Polynomial size proofs of the propositional pigeonhole principle

Journal of Symbolic Logic 52 (4):916-927 (1987)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 92,813

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

38 (#430,559)

6 months
11 (#270,674)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
A lower bound for intuitionistic logic.Pavel Hrubeš - 2007 - Annals of Pure and Applied Logic 146 (1):72-90.
Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
On lengths of proofs in non-classical logics.Pavel Hrubeš - 2009 - Annals of Pure and Applied Logic 157 (2-3):194-205.

View all 30 citations / Add more citations

References found in this work

No references found.

Add more references