Abstract

We describe a general method how to construct from a propositional proof system P a possibly much stronger proof system iP. The system iP operates with exponentially long P-proofs described "implicitly" by polynomial size circuits. As an example we prove that proof system iEF, implicit EF, corresponds to bounded arithmetic theory $V_{2}^{1}$ and hence, in particular, polynomially simulates the quantified propositional calculus G and the $\pi_{1}^{b}-consequences$ of $S_{2}^{1}$ proved with one use of exponentiation. Furthermore, the soundness of iEF is not provable in $S_{2}^{1}$ . An iteration of the construction yields a proof system corresponding to $T_{2} + Exp$ and, in principle, to much stronger theories