Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

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

Paper:

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
pigeon hole principle, with $n$ holes and any number of
pigeons, is of length $\Omega(2^{n^{\epsilon}})$,
(for some global constant $\epsilon > 0$).