We prove that any Resolution proof for the weak pigeon hole 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 N P ⊄ P/poly does not have short Resolution proofs.
|Original language||English (US)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 2002|
|Event||Proceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada|
Duration: May 19 2002 → May 21 2002
All Science Journal Classification (ASJC) codes