__
Revision #1 to TR01-021 | 3rd February 2002 00:00
__
#### Resolution Lower Bounds for the Weak Pigeonhole Principle Revision of: TR01-021

Revision #1
Authors:

Ran Raz
Accepted on: 3rd February 2002 00:00

Downloads: 989

Keywords:

**Abstract:**

We prove that any Resolution proof for the weak pigeon hole principle,

with $n$ holes and any number of pigeons, is of length

$\Omega(2^{n^{\epsilon}})$, (for some global constant $\epsilon > 0$).

One corollary is that a certain propositional formulation of

the statement $NP \not \subset P/poly$ does not have short Resolution proofs.

__
TR01-021 | 7th March 2001 00:00
__

#### Resolution Lower Bounds for the Weak Pigeonhole Principle

TR01-021
Authors:

Ran Raz
Publication: 7th March 2001 17:03

Downloads: 1321

Keywords:

**Abstract:**
We prove that any Resolution proof for the weak

pigeon hole principle, with $n$ holes and any number of

pigeons, is of length $\Omega(2^{n^{\epsilon}})$,

(for some global constant $\epsilon > 0$).