[Proof Complexity] Paper available (Quasipoly size Frege proofs of PHP)

Sam Buss sbuss at math.ucsd.edu
Thu Sep 18 04:08:39 CEST 2014

Dear colleagues,

I have posted a new preprint, "Quasipolynomial Size Proofs of the
Propositional Pigeonhole Principle", available from
http://www.math.ucsd.edu/~sbuss/ResearchWeb/QuasiPolyPHP/.  (The direct link
to the PDF is

Comments, suggestions, corrections are appreciated.

Best regards, Sam

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 instead of counting. 

More information about the Proof-Complexity mailing list