An exponential separation between the parity principle and the pigeonhole principle

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 (1990) 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 (see Papadimitriou, 1991). In particular, oracle separations between the complexity classes PPA and PPAD, and between PPA and PPP also follow from our techniques (Beame et al., 1995).     

Regular Resolution Lower Bounds For The Weak Pigeonhole Principle

We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length , (for some global constant > 0).* Research supported by NSF grant CCR-9820831, US-Israel BSF grant 98-00349, and an NSERC grant. Research supported by US-Israel BSF grant 98-00349, and NSF grant CCR-9987077.