𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A New Proof of the Weak Pigeonhole Principle

✍ Scribed by Alexis Maciel; Toniann Pitassi; Alan R. Woods

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
213 KB
Volume
64
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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. Their argument was further refined by J. KrajΔ± Β΄c Λ‡ek (J. Symbolic Logic 59 (1994), 73-86). In this paper, we present a new proof: we show that the weak pigeonhole principle has quasipolynomial-size LK 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.

πŸ“œ SIMILAR VOLUMES

The weak pigeonhole principle for functi
The weak pigeonhole principle for function classes in S12
✍ Norman Danner; Chris Pollett πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 199 KB πŸ‘ 1 views

## Abstract It is well known that __S__ ^1^~2~ cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability of the surjective (dual) weak pigeonhole principle in __S__ ^1^~2~ for provably weaker function class

A new proof of the invariance principle
A new proof of the invariance principle in scattering theory
✍ John D Dollard; Charles N Friedman πŸ“‚ Article πŸ“… 1979 πŸ› Elsevier Science 🌐 English βš– 220 KB

For free and interacting Hamiltonians, Ho and H = H,, + V(r) acting in L2(R3, dx) with V(r) a radial potential satisfying certain technical conditions, and for 9) a real function on R with v' > 0 except on a discrete set, we prove that the Moller wave operators Q\* = strong limit eiWHJ e-ifVtHo) t-?

Monotone Proofs of the Pigeon Hole Princ
Monotone Proofs of the Pigeon Hole Principle
✍ Albert Atserias; Nicola Galesi; Ricard GavaldΓ  πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 218 KB