We prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length Ω(2 n∈), (for some global constant ∈ > 0).
|Original language||English (US)|
|Number of pages||22|
|State||Published - 2004|
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics