Abstract
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-off 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, Pitassi and Woods (2000). Our technique requires formalizing the ideas underlying Nepomnjaščij’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.
Supported by the CUR, Generalitat de Catalunya, through grant 1999FI 00532. Partially supported by ALCOM-FT, IST-99-14186.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Ajtai. The complexity of the pigeonhole principle. In 29th Annual IEEE Symposium on Foundations of Computer Science, pages 346–355, 1988.
A. Berarducci and B. Intrigila. Combinatorial principles in elementary number theory. Annals of Pure and Applied Logic, 55:35–50, 1991.
S. R. Buss. Polynomial size proofs of the propositional pigeonhole principle. Journal of Symbolic Logic, 52(4):916–927, 1997.
S. R. Buss and G. Turán. Resolution proofs of generalized pigeonhole principles. Theoretical Computer Science, 62:311–317, 1988.
S. Cook and R. Reckhow. The relative efficiency of propositional proof systems. Journal of Symbolic Logic, 44:36–50, 1979.
L. Fortnow. Time-space tradeoffs for satisfiability. In 12th IEEE Conference in Computational Complexity, pages 52–60, 1997. To appear in Journal of Computer and System Sciences.
L. Fortnow and D. van Meldebeek. Time-space tradeoffs for non-deterministic computation. In 15th IEEE Conference in Computational Complexity, 2000.
H. Gaifman and C. Dimitracopoulos. Fragments of Peano’s arithmetic and the MRDP theorem. In Logic and algorithmic, number 30 in Monographies de l’Enseignement Mathématique, pages 187–206. Univeristé de Genève, 1982.
P. Hájek and P. Pudlák. Metamathematics of First-Order Arithmetic. Springer, 1993.
A. Haken. The intractability of resolution. Theoretical Computer Science, 39:297–308, 1985.
W. Hesse. Division is in uniform TC 0. To appear in ICALP’01, 2001.
J. Krajícek. Bounded arithmetic, propositional logic, and complexity theory. Cambridge University Press, 1995.
J. Krajícek, P. Pudlák, and A. Woods. Exponential lower bound to the size of bounded depth frege proofs of the pigeon hole principle. Random Structures and Algorithms, 7(1):15–39, 1995.
R. J. Lipton and A. Viglas. On the complexity of SAT. In 40th Annual IEEE Symposium on Foundations of Computer Science, pages 459–464, 1999.
A. Maciel, T. Pitassi, and A. R. Woods. A new proof of the weak pigeonhole principle. In 32th Annual ACM Symposium on the Theory of Computing, 2000.
A. J. Macintyre and D. Marker. Primes and their residue rings in models of open induction. Annals of Pure and Applied Logic, 43(1):57–77, 1989.
V. A. Nepomnjaščij. Rudimentary predicates and Turing calculations. Soviet Math. Dokl., 11:1462–1465, 1970.
J. B. Paris, A. J. Wilkie, and A. R. Woods. Provability of the pigeonhole principle and the existence of infinitely many primes. Journal of Symbolic Logic, 53(4):1235–1244, 1988.
T. Pitassi, P. Beame, and R. Impagliazzo. Exponential lower bounds for the pigeonhole principle. Computational Complexity, 3(2):97–140, 1993.
G. Takeuti. Proof Theory. North-Holland, second edition, 1987.
A. R. Woods. Some problems in logic and number theory, and their connections. PhD thesis, Univerity of Manchester, Department of Mathematics, 1981.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Atserias, A. (2001). Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms. In: Sgall, J., Pultr, A., Kolman, P. (eds) Mathematical Foundations of Computer Science 2001. MFCS 2001. Lecture Notes in Computer Science, vol 2136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44683-4_14
Download citation
DOI: https://doi.org/10.1007/3-540-44683-4_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42496-3
Online ISBN: 978-3-540-44683-5
eBook Packages: Springer Book Archive