The complexity of the Pigeonhole Principle

Abstract

The Pigeonhole Principle for n is the statement that there is no one-to-one function between a set of size n and a set of size n-1. This statement can be formulated as an unlimited fan-in constant depth polynomial size Boolean formula PHPn in n(n-1) variables. We may think that the truth-value of the variable xi,j will be true iff the function maps the i-th element of the first set to the j-th element of the second (see Cook and Rechkow [5]). PHPn can be proved in the propositional calculus. That is, a sequence of Boolean formulae can be given so that each one is either an axiom of the propositional calculus or a consequence of some of the previous ones according to an inference rule of the propositional calculus, and the last one is PHPn. Our main result is that the Pigeonhole Principle cannot be proved this way, if the size of the proof (the total number or symbols of the formulae in the sequence) is polynomial in n and each formula is constant depth (unlimited fan-in), polynomial size and contains only the variables of PHPn. © 1994 Akadémiai Kiadó.