Journal of Symbolic Logic · 1987 · 194 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsLogicTheory Of ComputationPigeonhole PrinciplePredicate LogicProof ComplexityTheorem ProvingFrege SystemsProof Size Lower BoundsPropositional Reasoning
Abstract Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.
7
The intractability of resolution
Armin Haken · Theoretical Computer Science · 1985 · 829 citations
The relative efficiency of propositional proof systems
Stephen Cook, Robert A. Reckhow · Journal of Symbolic Logic · 1979 · 827 citations
Separating the polynomial-time hierarchy by oracles
Andrew Chi-Chih Yao · 1985 · 554 citations
Alasdair Urquhart · Journal of the ACM · 1987 · 451 citations · Full text
Mathematics and Computers in Simulation · 1979 · 262 citations