An exponential separation between the matching principle and the pigeonhole principle
- 30 December 2002
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 308-319
- https://doi.org/10.1109/lics.1993.287577
Abstract
The combinatorial matching principle states that there is no perfect matching on an oddnumber of vertices. This principle generalizes the pigeonhole principle, which states thatfor a fixed bi-partition of the vertices, there is no perfect matching between them. Therefore,it follows from recent lower bounds for the pigeonhole principle that the matchingprinciple requires exponential-size bounded-depth Frege proofs. Ajtai [Ajt90] previouslyshowed that the matching principle does not have...Keywords
This publication has 9 references indexed in Scilit:
- Exponential lower bounds for the pigeonhole principlecomputational complexity, 1993
- Approximation and Small-Depth Frege ProofsSIAM Journal on Computing, 1992
- Exponential lower bounds for the pigeonhole principlePublished by Association for Computing Machinery (ACM) ,1992
- On Inefficient Proofs of Existence and Complexity ClassesPublished by Elsevier BV ,1992
- Parity and the Pigeonhole PrinciplePublished by Springer Science and Business Media LLC ,1990
- Optimal bounds for decision problems on the CRCW PRAMJournal of the ACM, 1989
- The complexity of the pigeonhole principlePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Hard examples for resolutionJournal of the ACM, 1987
- The relative efficiency of propositional proof systemsThe Journal of Symbolic Logic, 1979