Polynomial size proofs of the propositional pigeonhole principle

Samuel R. Buss

Journal of Symbolic Logic · 1987 · 194 citations · 7 references

Concepts

Abstract

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.

References

7