Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms
✍ Scribed by Albert Atserias
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 158 KB
- Volume
- 295
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
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 al. (Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing, 2000). Our technique requires formalizing the ideas underlying NepomnjaÄ sÄ cij's Theorem which might be of independent interest. Moreover, our result implies a proof of the unboundedness of primes in I 0 with a provably weaker 'large number assumption' than previously needed.