{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:24Z","timestamp":1781078304665,"version":"3.54.1"},"reference-count":12,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":9598,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1987,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.2307\/2273826","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:23:41Z","timestamp":1146954221000},"page":"916-927","source":"Crossref","is-referenced-by-count":118,"title":["Polynomial size proofs of the propositional pigeonhole principle"],"prefix":"10.1017","volume":"52","author":[{"given":"Samuel R.","family":"Buss","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200029315_ref011","doi-asserted-by":"publisher","DOI":"10.1145\/7531.8928"},{"key":"S0022481200029315_ref009","volume-title":"Talk presented at Logic Colloquium '84","author":"Wilkie","year":"1984"},{"key":"S0022481200029315_ref006","volume-title":"The complexity of computing","author":"Savage","year":"1976"},{"key":"S0022481200029315_ref004","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90144-6"},{"key":"S0022481200029315_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075316"},{"key":"S0022481200029315_ref010","unstructured":"Woods A. , Some problems in logic and number theory and their connections, Ph.D. Thesis, Manchester University, Manchester, 1981."},{"key":"S0022481200029315_ref008","first-page":"234","volume-title":"Zapiski Nauchnykh Seminarov LOMI","volume":"8","author":"Tse\u012dtin","year":"1968"},{"key":"S0022481200029315_ref002","first-page":"36","volume":"44","author":"Cook","year":"1979","journal-title":"The relative efficiency of propositional proof systems"},{"key":"S0022481200029315_ref003","first-page":"260","article-title":"Parity, circuits and the polynomial-time hierarchy","volume":"22","author":"Furst","year":"1981","journal-title":"IEEE Symposium on Foundation of Computing"},{"key":"S0022481200029315_ref001","unstructured":"Buss S. , Bounded arithmetic, Ph.D. Thesis, Princeton University, Princeton, New Jersey, 1985."},{"key":"S0022481200029315_ref012","first-page":"1","article-title":"Separating the polynomial-time hierarchy by oracles","volume":"26","author":"Yao","year":"1985","journal-title":"IEEE Symposium on Foundations of Computing"},{"key":"S0022481200029315_ref007","first-page":"505","volume-title":"Logic Colloquium '76","author":"Statman","year":"1977"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200029315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,20]],"date-time":"2019-05-20T21:17:09Z","timestamp":1558387029000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200029315\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,12]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1987,12]]}},"alternative-id":["S0022481200029315"],"URL":"https:\/\/doi.org\/10.2307\/2273826","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,12]]}}}