On the computational content of intuitionistic propositional proofs

✍ Scribed by Samuel R Buss; Pavel Pudlák

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 115 KB
• Volume: 109
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(01)00040-9

✦ Synopsis

The paper proves reÿned feasibility properties for the disjunction property of intuitionistic propositional logic. We prove that it is possible to eliminate all cuts from an intuitionistic proof, propositional or ÿrst-order, without increasing the Horn closure of the proof. We obtain a polynomial time, interactive, realizability algorithm for propositional intuitionistic proofs. The feasibility of the disjunction property is proved for sequents containing Harrop formulas. Under hardness assumptions for NP and for factoring, it is shown that the intuitionistic propositional calculus does not always have polynomial size proofs and that the classical propositional calculus provides a superpolynomial speedup over the intuitionistic propositional calculus. The disjunction property for intuitionistic propositional logic is proved to be P-hard by a reduction to the circuit value problem.