Title :
Resolution lower bounds for the weak pigeon hole principle
Author_Institution :
Dept. of Comput. Sci., Weizmann Inst. of Sci., Rehovot
fDate :
6/24/1905 12:00:00 AM
Abstract :
We prove that any resolution proof for the weak pigeonhole principle, with n holes and any number of pigeons, is of length Ω(2n∈), (for some constant ∈ > 0). One corollary is that a certain propositional formulation of the statement NP ⊄ P/poly does not have short resolution proofs
Keywords :
combinatorial mathematics; computational complexity; theorem proving; propositional formulation; resolution lower bounds; weak pigeonhole principle; Computational complexity; Computer aided software engineering; Computer science; Polynomials;
Conference_Titel :
Computational Complexity, 2002. Proceedings. 17th IEEE Annual Conference on
Conference_Location :
Montreal, Que.
Print_ISBN :
0-7695-1468-5
DOI :
10.1109/CCC.2002.1004322
