Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-055 | 26th July 2001 00:00

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

TR01-055
Authors: Alexander Razborov
Publication: 26th July 2001 16:49
Keywords:

Abstract:

Recently, 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$).

ISSN 1433-8092 | Imprint