In the paper we consider complexity of intuitionistic propositional logic and its natural fragments such as implicative fragment, finite-variable fragments, and some others. Most facts we mention here are known and obtained by logicians from different countries and in different time since 1920s; we present these results together to see the whole picture.

S4.2 is the modal logic of directed partial pre-orders and/or the modal logic of reflexive and transitive relational frames with a final cluster. It holds a distinguished position in philosophical...