Resolution lower bounds for the weak pigeonhole principle

Ran Raz

doi:10.1145/509984.509987

Resolution lower bounds for the weak pigeonhole principle

Ran Raz

Research output: Contribution to journal › Conference article › peer-review

19 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^nε), (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)
Pages (from-to)	553-562
Number of pages	10
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/509984.509987
State	Published - 2002
Externally published	Yes
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

Software

Access to Document

10.1145/509984.509987

Cite this

@article{3f32364e340543b68ff87958d313f764,

title = "Resolution lower bounds for the weak pigeonhole principle",

abstract = "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.",

author = "Ran Raz",

year = "2002",

doi = "10.1145/509984.509987",

language = "English (US)",

pages = "553--562",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

note = "Proceedings of the 34th Annual ACM Symposium on Theory of Computing ; Conference date: 19-05-2002 Through 21-05-2002",

}

TY - JOUR

T1 - Resolution lower bounds for the weak pigeonhole principle

AU - Raz, Ran

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036036844&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036036844&partnerID=8YFLogxK

U2 - 10.1145/509984.509987

DO - 10.1145/509984.509987

M3 - Conference article

AN - SCOPUS:0036036844

SN - 0734-9025

SP - 553

EP - 562

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 34th Annual ACM Symposium on Theory of Computing

Y2 - 19 May 2002 through 21 May 2002

ER -

Resolution lower bounds for the weak pigeonhole principle

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this