ECCC-Report TR01-021https://eccc.weizmann.ac.il/report/2001/021Comments and Revisions published for TR01-021en-usSun, 03 Feb 2002 00:00:00 +0200
Revision 1
| Resolution Lower Bounds for the Weak Pigeonhole Principle Revision of: TR01-021 |
Ran Raz
https://eccc.weizmann.ac.il/report/2001/021#revision1
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.
Sun, 03 Feb 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2001/021#revision1
Paper TR01-021
| Resolution Lower Bounds for the Weak Pigeonhole Principle |
Ran Raz
https://eccc.weizmann.ac.il/report/2001/021We 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$).
Wed, 07 Mar 2001 17:03:47 +0200https://eccc.weizmann.ac.il/report/2001/021