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

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 No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2307/2273826
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 52,768
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

A Lower Bound for Intuitionistic Logic.Pavel Hrubeš - 2007 - Annals of Pure and Applied Logic 146 (1):72-90.
On Lengths of Proofs in Non-Classical Logics.Pavel Hrubeš - 2009 - Annals of Pure and Applied Logic 157 (2-3):194-205.
Some More Curious Inferences.Jeffrey Ketland - 2005 - Analysis 65 (1):18–24.

View all 23 citations / Add more citations

Similar books and articles

Analytics

Added to PP index
2009-01-28

Total views
19 ( #513,601 of 2,340,352 )

Recent downloads (6 months)
1 ( #514,582 of 2,340,352 )

How can I increase my downloads?

Downloads

My notes