Intuitionistic logic and the polynomial hierarchy
We conduct a complexity-theoretic study of focussed proof systems, relating the alternation of synchronous and asynchronous phases in a proof to an appropriate alternating time hierarchy, for instance the polynomial hierarchy. We propose a notion of ‘over-focussing’ that admits non-branching invertible rules during synchronous phases, due to the fact that deterministic computations can equally be carried out by a nondeterministic machine. As an application, we develop an over-focussed system for a fragment of intuitionistic propositional logic which we show to be already PSPACE-complete by a refinement of Statman’s translation from true QBFs. We show that this translation has a well-behaved inverse, preserving quantifier complexity, in the form of a QBF encoding of proof search for the over-focussed system, demonstrating the usefulness of considering such systems. Consequently we are able to delineate intuitionistic tautologies according to the polynomial hierarchy and derive further proof-theoretic consequences for intuitionistic logic.