Polynomial size proofs of the propositional pigeonhole principle
- 1 December 1987
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 52 (4) , 916-927
- https://doi.org/10.2307/2273826
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.Keywords
This publication has 5 references indexed in Scilit:
- Hard examples for resolutionJournal of the ACM, 1987
- The intractability of resolutionTheoretical Computer Science, 1985
- Counting problems in bounded arithmeticLecture Notes in Mathematics, 1985
- Separating the polynomial-time hierarchy by oraclesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Parity, circuits, and the polynomial-time hierarchyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981