next up previous
Next: About this document ...

Resolution width-size trade-offs for the Pigeon-Hole Principle

Stefan Dantchev

dantchev@dcs.qmul.ac.uk

BRICS1 , Dept. of Computer Science, University of Aarhus
Dept. of Computer Science, Queen Mary, University of London


Abstract:

We prove the following two results:

(1) There is a resolution proof of the Weak Pigeon-Hole Principle, $WPHP_{n}^{m}$ of size $2^{O\left(\frac{n\log n}{\log m}+\log m\right)}$ for any number of pigeons $m$ and any number of holes $n$ .

(2) Any resolution proof of $WPHP_{n}^{m}$ of width $\left(\frac{1}{16}-\varepsilon \right)n^{2}$ has to be of size $2^{\Omega \left(n\right)}$ , independently from $m$ .

These results give not only a resolution size-width tradeoff for the Weak Pigeon-Hole Principle, but also almost optimal such trade-off for resolution in general. The upper bound (1) may be of independent interest, as it has been known for the two extreme values of $m$ , $m=n+1$ and $m=2^{\sqrt{n\log n}}$ , only.



S. Dantchev 2002-12-13