Preprint:
Sam Buss
"Quasipolynomial Size Proofs of
the Propositional Pigeonhole Principle"
Theoretical Computer Science 576, C (2015) 77-84.
Download manuscript: PDF.
Abstract: Cook and Reckhow proved in 1979 that the propositional pigeonhole principle has polynomial size extended Frege proofs. Buss proved in 1987 that it also has polynomial size Frege proofs; these Frege proofs used a completely different proof method based on counting. This paper shows that the original Cook and Reckhow extended Frege proofs can be formulated as quasipolynomial size Frege proofs. The key point is that st-connectivity can be used to define the Cook-Reckhow construction.