Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR01-075 | 2nd November 2001 00:00

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

TR01-075
Authors: Alexander Razborov
Publication: 2nd November 2001 11:49
Downloads: 2665
Keywords:

Abstract:

We show that every resolution proof of the {\em functional} version
$FPHP^m_n$ of the pigeonhole principle (in which one pigeon may not split
between several holes) must have size $\exp\of{\Omega\of{\frac n{(\log m)^2}}}$. This implies an $\exp\of{\Omega(n^{1/3})}$ bound when the number
of pigeons $m$ is arbitrary.

ISSN 1433-8092 | Imprint