Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #1
Authors: Ran Raz
Accepted on: 3rd February 2002 00:00
Downloads: 952
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
Downloads: 1174
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$).



ISSN 1433-8092 | Imprint