A new proof of the weak pigeonhole principle
Alexis Maciel, Toniann Pitassi, Alan R. Woods · 2000
The exact complexity of the weak pigeonhole principle is an old and fundamental problem in proof complexity.Using a diagonalization argument, Paris, Wilkie and Woods [9] showed how to prove the weak pigeonhole principle with bounded-depth, quasipolynomial-size proofs.Their argument was further refined by Krajf~ek [5].In this paper, we present a new proof: we show that the the weak pigeonhole principle has quasipolynomial-size proofs where every formula consists of a single AND/OR. of polylog fan-in.Our proof is conceptually simpler than previous arguments, and is optimal with respect to depth.