Exponential lower bounds for the pigeonhole principle
- 1 January 1992
- proceedings article
- Published by Association for Computing Machinery (ACM)
- Vol. 3 (2) , 200-220
- https://doi.org/10.1145/129712.129733
Abstract
In this paper we prove an exponential lower bound on the size of bounded-depth Frege proofs for the pigeonhole principle (PHP). We also obtain an O(loglogn)-depth lower bound for any polynomial-sized Frege proof of the pigeonhole principle. Our theorem nearly completes the search for the exact complexity of the PHP, as S. Buss has constructed polynomial-size, logn-depth Frege proofs for the PHP. The main lemma in our proof can be viewed as a general Håstad-style Switching Lemma for restrictions that are partial matchings. Our lower bounds for the pigeonhole principle improve on previous superpolynomial lower bounds.Keywords
This publication has 0 references indexed in Scilit: