๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Resolution lower bounds for the weak functional pigeonhole principle

โœ Scribed by Alexander A. Razborov

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
243 KB
Volume
303
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis

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.

๐Ÿ“œ 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

Improved bounds on the Weak Pigeonhole P
Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms
โœ Albert Atserias ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 158 KB

We show that the known bounded-depth proofs of the Weak Pigeonhole Principle PHP 2n n in size n O(log(n)) are not optimal in terms of size. More precisely, we give a size-depth trade-o upper bound: there are proofs of size n O(d(log(n)) 2=d ) and depth O(d). This solves an open problem of Maciel et