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.

We define the notions of a canonical inference rule and a canonical system in the framework of single-conclusion Gentzen-type systems (or, equivalently, natural deduction systems), and prove that such a canonical system is non-trivial iff it is coherent (where coherence is a constructive condition). Next we develop a general non-deterministic Kripke-style semantics for such systems, and show that every constructive canonical system (i.e. coherent canonical single-conclusion system) induces a class of non-deterministic Kripke-style frames for which it is strongly sound and (...) complete. We use this non-deterministic semantics to show that all constructive canonical systems admit a strong form of the cut-elimination theorem. We also use it for providing a decision procedure for every such system. These results identify a large family of basic constructive connectives, each having both a proof-theoretical characterization in terms of a coherent set of canonical rules, as well as a semantic characterization using non-deterministic frames. The family includes the standard intuitionistic connectives, together with many other independent connectives. (shrink)