Resolution lower bounds for the weak pigeonhole principle

Ran Raz

doi:10.1145/972639.972640

Resolution lower bounds for the weak pigeonhole principle

Ran Raz

Research output: Contribution to journal › Article › peer-review

42 Scopus citations

Abstract

We prove that any Resolution proof for the weak pigeonhole principle, with n holes and any number of pigeons, is of length Ω2(2^nε), (for some global constant ε > 0). One corollary is that a certain prepositional formulation of the statement NP ⊄ P/ poly does not have short Resolution proofs.

Original language	English (US)
Pages (from-to)	115-138
Number of pages	24
Journal	Journal of the ACM
Volume	51
Issue number	2
DOIs	https://doi.org/10.1145/972639.972640
State	Published - Mar 2004
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Information Systems
Hardware and Architecture
Artificial Intelligence

Keywords

Computational complexity
Lower bounds
P different than NP
Prepositional logic
Proof complexity

Access to Document

10.1145/972639.972640

Cite this

@article{f6a6b3d1ebd4461892a193c611ade79b,

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

abstract = "We prove that any Resolution proof for the weak pigeonhole principle, with n holes and any number of pigeons, is of length Ω2(2nε), (for some global constant ε > 0). One corollary is that a certain prepositional formulation of the statement NP ⊄ P/ poly does not have short Resolution proofs.",

keywords = "Computational complexity, Lower bounds, P different than NP, Prepositional logic, Proof complexity",

author = "Ran Raz",

year = "2004",

month = mar,

doi = "10.1145/972639.972640",

language = "English (US)",

volume = "51",

pages = "115--138",

journal = "Journal of the ACM",

issn = "0004-5411",

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

number = "2",

}

TY - JOUR

T1 - Resolution lower bounds for the weak pigeonhole principle

AU - Raz, Ran

PY - 2004/3

Y1 - 2004/3

N2 - We prove that any Resolution proof for the weak pigeonhole principle, with n holes and any number of pigeons, is of length Ω2(2nε), (for some global constant ε > 0). One corollary is that a certain prepositional formulation of the statement NP ⊄ P/ poly does not have short Resolution proofs.

AB - We prove that any Resolution proof for the weak pigeonhole principle, with n holes and any number of pigeons, is of length Ω2(2nε), (for some global constant ε > 0). One corollary is that a certain prepositional formulation of the statement NP ⊄ P/ poly does not have short Resolution proofs.

KW - Computational complexity

KW - Lower bounds

KW - P different than NP

KW - Prepositional logic

KW - Proof complexity

UR - https://www.scopus.com/pages/publications/4243162038

UR - https://www.scopus.com/pages/publications/4243162038#tab=citedBy

U2 - 10.1145/972639.972640

DO - 10.1145/972639.972640

M3 - Article

AN - SCOPUS:4243162038

SN - 0004-5411

VL - 51

SP - 115

EP - 138

JO - Journal of the ACM

JF - Journal of the ACM

IS - 2

ER -

Resolution lower bounds for the weak pigeonhole principle

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this