About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Conference paper
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. PHPn can be proved in the propositional calculus; that is, a sequence of Boolean formulas 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, the last one being PHPn. The main result is that the pigeonhole principle cannot be proved in this way if the size of the proof (the total number or symbols of the formulas 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.