A parity-based Frege proof for the symmetric pigeonhole principle

Notre Dame Journal of Formal Logic 34 (4):597-601 (1993)
  Copy   BIBTEX

Abstract

Sam Buss produced the first polynomial size Frege proof of thepigeonhole principle. We introduce a variation of that problem and producea simpler proof based on parity. The proof appearing here has an upperbound that is quadratic in the size of the input formula.

Categories

Keywords

Reprint years

DOI

10.1305/ndjfl/1093633908

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,793

External links

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

Through your library

My notes

Similar books and articles

Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
An exponential separation between the parity principle and the pigeonhole principle.Paul Beame & Toniann Pitassi - 1996 - Annals of Pure and Applied Logic 80 (3):195-228.
Frege Proof System and TNC$^circ$.Gaisi Takeuti - 1998 - Journal of Symbolic Logic 63 (2):709-738.
Frege proof system and TNC°.Gaisi Takeuti - 1998 - Journal of Symbolic Logic 63 (2):709 - 738.
Frege's proof of referentiality.Øystein Linnebo - 2004 - Notre Dame Journal of Formal Logic 45 (2):73-98.
Quasipolynomial Size Frege Proofs of Frankl’s Theorem on the Trace of Sets.James Aisenberg, Maria Luisa Bonet & Sam Buss - 2016 - Journal of Symbolic Logic 81 (2):687-710.
Simplified Lower Bounds for Propositional Proofs.Alasdair Urquhart & Xudong Fu - 1996 - Notre Dame Journal of Formal Logic 37 (4):523-544.
Ramsey’s theorem for pairs, collection, and proof size.Leszek Aleksander Kołodziejczyk, Tin Lok Wong & Keita Yokoyama - 2023 - Journal of Mathematical Logic 24 (2).
Extension without cut.Lutz Straßburger - 2012 - Annals of Pure and Applied Logic 163 (12):1995-2007.

Analytics

Added to PP
2010-08-24

Downloads
26 (#835,533)

6 months
8 (#528,772)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references