{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:56Z","timestamp":1725490256382},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_14","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"148-158","source":"Crossref","is-referenced-by-count":3,"title":["Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms"],"prefix":"10.1007","author":[{"given":"Albert","family":"Atserias","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai. The complexity of the pigeonhole principle. In 29th Annual IEEE Symposium on Foundations of Computer Science, pages 346\u2013355, 1988.","DOI":"10.1109\/SFCS.1988.21951"},{"key":"14_CR2","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0168-0072(91)90096-5","volume":"55","author":"A. Berarducci","year":"1991","unstructured":"A. Berarducci and B. Intrigila. Combinatorial principles in elementary number theory. Annals of Pure and Applied Logic, 55:35\u201350, 1991.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"4","key":"14_CR3","doi-asserted-by":"crossref","first-page":"916","DOI":"10.2307\/2273826","volume":"52","author":"S. R. Buss","year":"1997","unstructured":"S. R. Buss. Polynomial size proofs of the propositional pigeonhole principle. Journal of Symbolic Logic, 52(4):916\u2013927, 1997.","journal-title":"Journal of Symbolic Logic"},{"key":"14_CR4","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(88)90072-2","volume":"62","author":"S. R. Buss","year":"1988","unstructured":"S. R. Buss and G. Tur\u00e1n. Resolution proofs of generalized pigeonhole principles. Theoretical Computer Science, 62:311\u2013317, 1988.","journal-title":"Theoretical Computer Science"},{"key":"14_CR5","doi-asserted-by":"publisher","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S. Cook","year":"1979","unstructured":"S. Cook and R. Reckhow. The relative efficiency of propositional proof systems. Journal of Symbolic Logic, 44:36\u201350, 1979.","journal-title":"Journal of Symbolic Logic"},{"key":"14_CR6","unstructured":"L. Fortnow. Time-space tradeoffs for satisfiability. In 12th IEEE Conference in Computational Complexity, pages 52\u201360, 1997. To appear in Journal of Computer and System Sciences."},{"key":"14_CR7","unstructured":"L. Fortnow and D. van Meldebeek. Time-space tradeoffs for non-deterministic computation. In 15th IEEE Conference in Computational Complexity, 2000."},{"key":"14_CR8","unstructured":"H. Gaifman and C. Dimitracopoulos. Fragments of Peano\u2019s arithmetic and the MRDP theorem. In Logic and algorithmic, number 30 in Monographies de l\u2019Enseignement Math\u00e9matique, pages 187\u2013206. Univerist\u00e9 de Gen\u00e8ve, 1982."},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"P. H\u00e1jek and P. Pudl\u00e1k. Metamathematics of First-Order Arithmetic. Springer, 1993.","DOI":"10.1007\/978-3-662-22156-3"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(85)90144-6","volume":"39","author":"A. Haken","year":"1985","unstructured":"A. Haken. The intractability of resolution. Theoretical Computer Science, 39:297\u2013308, 1985.","journal-title":"Theoretical Computer Science"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"W. Hesse. Division is in uniform TC 0. To appear in ICALP\u201901, 2001.","DOI":"10.1007\/3-540-48224-5_9"},{"key":"14_CR12","doi-asserted-by":"crossref","unstructured":"J. Kraj\u00edcek. Bounded arithmetic, propositional logic, and complexity theory. Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511529948"},{"issue":"1","key":"14_CR13","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1002\/rsa.3240070103","volume":"7","author":"J. Kraj\u00edcek","year":"1995","unstructured":"J. Kraj\u00edcek, P. Pudl\u00e1k, 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\u201339, 1995.","journal-title":"Random Structures and Algorithms"},{"key":"14_CR14","doi-asserted-by":"crossref","unstructured":"R. J. Lipton and A. Viglas. On the complexity of SAT. In 40th Annual IEEE Symposium on Foundations of Computer Science, pages 459\u2013464, 1999.","DOI":"10.1109\/SFFCS.1999.814618"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1145\/335305.335348"},{"issue":"1","key":"14_CR16","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0168-0072(89)90025-0","volume":"43","author":"A. J. Macintyre","year":"1989","unstructured":"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\u201377, 1989.","journal-title":"Annals of Pure and Applied Logic"},{"key":"14_CR17","first-page":"1462","volume":"11","author":"V. A. Nepomnja\u0161\u010dij","year":"1970","unstructured":"V. A. Nepomnja\u0161\u010dij. Rudimentary predicates and Turing calculations. Soviet Math. Dokl., 11:1462\u20131465, 1970.","journal-title":"Soviet Math. Dokl."},{"issue":"4","key":"14_CR18","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.2307\/2274618","volume":"53","author":"J. B. Paris","year":"1988","unstructured":"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\u20131244, 1988.","journal-title":"Journal of Symbolic Logic"},{"issue":"2","key":"14_CR19","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01200117","volume":"3","author":"T. Pitassi","year":"1993","unstructured":"T. Pitassi, P. Beame, and R. Impagliazzo. Exponential lower bounds for the pigeonhole principle. Computational Complexity, 3(2):97\u2013140, 1993.","journal-title":"Computational Complexity"},{"key":"14_CR20","unstructured":"G. Takeuti. Proof Theory. North-Holland, second edition, 1987."},{"key":"14_CR21","unstructured":"A. R. Woods. Some problems in logic and number theory, and their connections. PhD thesis, Univerity of Manchester, Department of Mathematics, 1981."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:27:54Z","timestamp":1556818074000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_14","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}