ECCC-Report TR01-055https://eccc.weizmann.ac.il/report/2001/055Comments and Revisions published for TR01-055en-usThu, 26 Jul 2001 16:49:56 +0300
Paper TR01-055
| Improved Resolution Lower Bounds for the Weak Pigeonhole Principle |
Alexander Razborov
https://eccc.weizmann.ac.il/report/2001/055Recently, Raz established exponential lower bounds on the size
of resolution proofs of the weak pigeonhole principle. We give another
proof of this result which leads to better numerical bounds. Specifically,
we show that every resolution proof of $PHP^m_n$ must have size
$\exp\of{\Omega(n/\log m)^{1/2}}$ which implies an
$\exp\of{\Omega(n^{1/3})}$ bound when the number of pigeons $m$ is
arbitrary.
As a step toward extending this bound to the {\em functional} version of
$PHP^m_n$ (in which one pigeon may not split between several holes), we
introduce one intermediate version (in the form of a $PHP$-oriented
calculus) which, roughly speaking, allows arbitrary ``monotone reasoning''
about the location of an individual pigeon. For this version we prove an
$\exp\of{\Omega(n/\log^2 m)^{1/2}}$ lower bound
($\exp\of{\Omega(n^{1/4})}$ for arbitrary $m$).
Thu, 26 Jul 2001 16:49:56 +0300https://eccc.weizmann.ac.il/report/2001/055