{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T14:08:58Z","timestamp":1781014138660,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540544876","type":"print"},{"value":"9783540384014","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54487-9_67","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:53:41Z","timestamp":1330210421000},"page":"308-317","source":"Crossref","is-referenced-by-count":10,"title":["Ramsey's theorem in bounded arithmetic"],"prefix":"10.1007","author":[{"given":"Pavel","family":"Pudl\u00e1k","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"19_CR1","unstructured":"M.Ajtai, The complexity of the pigeonhole principle, 29-th Symp. on Foundations of Comp. Sci. (1988), pp. 346\u2013355."},{"key":"19_CR2","unstructured":"S. Buss, Bounded Arithmetic, Bibliopolis, 1986."},{"key":"19_CR3","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","volume":"44","author":"S.A. Cook","year":"1979","unstructured":"S.A. Cook, R.A. Reckhow, The relative efficiency of propositional proof systems, Journ. Symb. Logic 44, (1979), pp.36\u201350.","journal-title":"Journ. Symb. Logic"},{"issue":"4","key":"19_CR4","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579457","volume":"1","author":"P. Frankl","year":"1981","unstructured":"P. Frankl, R.M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1(4), (1981), pp.357\u2013368.","journal-title":"Combinatorica"},{"key":"19_CR5","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, Theor. Comp. Sci. 39, (1985), pp.297\u2013308.","journal-title":"Theor. Comp. Sci."},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"J.Kraj\u00ed\u010dek, P.Pudl\u00e1k, G.Takeuti, Bounded arithmetic and the polynomial hierarchy, Annals of Pure and Applied Logic, to appear.","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"19_CR7","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF00265682","volume":"22","author":"B. Krishnamurthy","year":"1985","unstructured":"B. Krishnamurthy, Short proofs for tricky formulas, Acta Informatica 22, (1985), pp.253\u2013275.","journal-title":"Acta Informatica"},{"key":"19_CR8","unstructured":"J.Paris, A.Wilkie, \u03940 sets and induction, in Proc. Jadwisin Logic Conference, Poland, Leeds Univ. Press, 1981, pp.237\u2013248."},{"key":"19_CR9","doi-asserted-by":"crossref","first-page":"67","DOI":"10.4064\/fm-127-1-67-76","volume":"127","author":"J. Paris","year":"1987","unstructured":"J. Paris, A. Wilkie, Counting \u0394 0 sets, Fundamenta Mathematicae 127, (1987), pp. 67\u201376.","journal-title":"Fundamenta Mathematicae"},{"key":"19_CR10","first-page":"1235","volume":"53\/4","author":"J.B. Paris","year":"1988","unstructured":"J.B. Paris, A,J, Wilkie and A.R. Woods, Provability of the Pigeon Hole Principle and the existence of infinitely many primes, JSL 53\/4, (1988), pp. 1235\u20131244.","journal-title":"JSL"},{"key":"19_CR11","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF00279952","volume":"25","author":"P. Pudl\u00e1k","year":"1988","unstructured":"P. Pudl\u00e1k, V. R\u00f6dl, P. Savick\u00fd, Graph complexity, Acta Informatica 25, (1988), pp.515\u2013535.","journal-title":"Acta Informatica"},{"key":"19_CR12","unstructured":"A.A.Razborov, Formulas of bounded depth in basis {&, \u2295} and some combinatorial problems, in Slo\u017enost' algoritmov i prikladnaja matemati\u010deskaja logika, S.I.Adjan editor, 1987."},{"key":"19_CR13","unstructured":"S.Toda, On the computational power of PP and \u2295PP, 30-th Symp. on Foundations of Comp. Sci., (1989), pp.514\u2013519."}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54487-9_67.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T14:06:56Z","timestamp":1713622016000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54487-9_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544876","9783540384014"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-54487-9_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}