On the weak pigeonhole principle
Jan Krajı́ček · Fundamenta Mathematicae · 2001
We investigate the proof complexity, in (extensions of) resolution and in bounded arithmetic, of the weak pigeonhole principle and of the Ramsey theorem. In particular, we link the proof complexities of these two principles. Further we give lower bounds t