An exponential separation between the parity principle and the pigeonhole principle

Annals of Pure and Applied Logic 80 (3):195-228 (1996)

Abstract
The combinatorial parity principle states that there is no perfect matching on an odd number of vertices. This principle generalizes the pigeonhole principle, which states that for a fixed bipartition of the vertices, there is no perfect matching between them. Therefore, it follows from recent lower bounds for the pigeonhole principle that the parity principle requires exponential-size bounded-depth Frege proofs. Ajtai previously showed that the parity principle does not have polynomial-size bounded-depth Frege proofs even with the pigeonhole principle as an axiom schema. His proof utilizes nonstandard model theory and is nonconstructive. We improve Ajtai's lower bound from barely superpolynomial to exponential and eliminate the nonstandard model theory. Our lower bound is also related to the inherent complexity of particular search classes . In particular, oracle separations between the complexity classes PPA and PPAD, and between PPA and PPP also follow from our techniques
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(96)83747-x
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


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

References found in this work BETA

Add more references

Citations of this work BETA

Propositional Proofs and Reductions Between NP Search Problems.Samuel R. Buss & Alan S. Johnson - 2012 - Annals of Pure and Applied Logic 163 (9):1163-1182.

Add more citations

Similar books and articles

Matrix Identities and the Pigeonhole Principle.Michael Soltys & Alasdair Urquhart - 2004 - Archive for Mathematical Logic 43 (3):351-357.
Isols and the Pigeonhole Principle.J. C. E. Dekker & E. Ellentuck - 1989 - Journal of Symbolic Logic 54 (3):833-846.
The Weak Pigeonhole Principle for Function Classes in S12.Norman Danner & Chris Pollett - 2006 - Mathematical Logic Quarterly 52 (6):575-584.
A Parity-Based Frege Proof for the Symmetric Pigeonhole Principle.Steve Firebaugh - 1993 - Notre Dame Journal of Formal Logic 34 (4):597-601.
Classical Linear Logics with Mix Separation Principle.Norihiro Kamide - 2003 - Mathematical Logic Quarterly 49 (2):201-209.

Analytics

Added to PP index
2014-01-16

Total views
3 ( #1,235,659 of 2,311,316 )

Recent downloads (6 months)
1 ( #753,648 of 2,311,316 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature