𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the inconsistency of a weak version of the libertarian principle

✍ Scribed by Ruvin Gekker


Book ID
116099682
Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
360 KB
Volume
18
Category
Article
ISSN
0165-1765

No coin nor oath required. For personal study only.


πŸ“œ SIMILAR VOLUMES


A New Proof of the Weak Pigeonhole Princ
✍ 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.