Resolution lower bounds for the weak pigeonhole principle

Research output: Contribution to journalConference article

18 Scopus citations

Abstract

We prove that any Resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length Ω(2), (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 languageEnglish (US)
Pages (from-to)553-562
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2002
Externally publishedYes
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

All Science Journal Classification (ASJC) codes

  • Software

Cite this