𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Resolution proofs of generalized pigeonhole principles

✍ Scribed by Samuel R. Buss; Győrgy Turán

Publisher
Elsevier Science
Year
1988
Tongue
English
Weight
690 KB
Volume
62
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

A New Proof of the Weak Pigeonhole Princ
A New Proof of the Weak Pigeonhole Principle
✍ Alexis Maciel; Toniann Pitassi; Alan R. Woods 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 213 KB

The exact complexity of the weak pigeonhole principle is an old and fundamental problem in proof complexity. Using a diagonalization argument, J. B. Paris et al. (J. Symbolic Logic 53 (1988), 1235-1244) showed how to prove the weak pigeonhole principle with bounded-depth, quasipolynomialsize proofs.

Resolution lower bounds for the weak fun
Resolution lower bounds for the weak functional pigeonhole principle
✍ Alexander A. Razborov 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 243 KB

We show that every resolution proof of the functional version FPHP m n of the pigeonhole principle (in which one pigeon may not split between several holes) must have size exp( (n=(log m) 2 )). This implies an exp( (n 1=3 )) bound when the number of pigeons m is arbitrary.