{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T14:08:57Z","timestamp":1781014137676,"version":"3.54.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2010,10,12]],"date-time":"2010-10-12T00:00:00Z","timestamp":1286841600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s00153-010-0212-9","type":"journal-article","created":{"date-parts":[[2010,10,13]],"date-time":"2010-10-13T08:13:26Z","timestamp":1286957606000},"page":"245-255","source":"Crossref","is-referenced-by-count":8,"title":["A note on propositional proof complexity of some Ramsey-type statements"],"prefix":"10.1007","volume":"50","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2010,10,12]]},"reference":[{"key":"212_CR1","unstructured":"Aehlig, K., Beckmann, A.: A remark on the induction needed to prove the Ramsey principle, unpublished manuscript (2006)"},{"key":"212_CR2","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: The complexity of the pigeonhole principle. In: Proceedings IEEE 29th Annual Symp. on Foundation of Computer Science, pp. 346\u2013355 (1988)","DOI":"10.1109\/SFCS.1988.21951"},{"key":"212_CR3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1006\/jcss.1998.1575","volume":"57","author":"P. Beame","year":"1998","unstructured":"Beame P., Cook S.A., Edmonds J., Impagliazzo R., Pitassi T.: The relative complexity of NP search problems. J. Comput. Syst. Sci. 57, 3\u201319 (1998)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"212_CR4","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s001530050118","volume":"38","author":"M. Chiari","year":"1999","unstructured":"Chiari M., Kraj\u00ed\u010dek J.: Lifting independence results in bounded arithmetic. Arch. Math. Log. 38(2), 123\u2013138 (1999)","journal-title":"Arch. Math. Log."},{"key":"212_CR5","doi-asserted-by":"crossref","unstructured":"Dantchev, S., Riis, S.: On Complexity gaps for Resolution-based proof systems, In: 12th Annual Conf. of the EACSL, Computer Sci Logic, LNCS 2903, pp. 142\u2013154. Springer (2003)","DOI":"10.1007\/978-3-540-45220-1_14"},{"key":"212_CR6","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","volume":"53","author":"P. Erd\u00f6s","year":"1947","unstructured":"Erd\u00f6s P.: Some remarks on the theory of graphs. Bull. AMS 53, 292\u2013294 (1947)","journal-title":"Bull. AMS"},{"key":"212_CR7","doi-asserted-by":"crossref","unstructured":"Hanika, J.: Search Problems and Bounded Arithmetic, PhD Thesis, Charles University, Prague (2004)","DOI":"10.1002\/malq.200410005"},{"issue":"6","key":"212_CR8","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1002\/malq.200410005","volume":"50","author":"J. Hanika","year":"2004","unstructured":"Hanika J.: Herbrandizing search problems in Bounded Arithmetic. Math. Log. Q. 50(6), 577\u2013586 (2004)","journal-title":"Math. Log. Q."},{"issue":"1","key":"212_CR9","doi-asserted-by":"crossref","first-page":"73","DOI":"10.2307\/2275250","volume":"59","author":"J. Kraj\u00ed\u010dek","year":"1994","unstructured":"Kraj\u00ed\u010dek J.: Lower bounds to the size of constant-depth propositional proofs. J. Symbolic Log. 59(1), 73\u201386 (1994)","journal-title":"J. Symbolic Log."},{"key":"212_CR10","doi-asserted-by":"crossref","unstructured":"Kraj\u00ed\u010dek, J.: Bounded arithmetic, propositional logic, and complexity theory, Encyclopedia of Mathematics and its applications, Vol. 60, Cambridge University Press (1995)","DOI":"10.1017\/CBO9780511529948"},{"issue":"1\u20133","key":"212_CR11","doi-asserted-by":"crossref","first-page":"123","DOI":"10.4064\/fm170-1-8","volume":"170","author":"J. Kraj\u00ed\u010dek","year":"2001","unstructured":"Kraj\u00ed\u010dek J.: On the weak pigeonhole principle. Fundamenta Mathematicae 170(1\u20133), 123\u2013140 (2001)","journal-title":"Fundamenta Mathematicae"},{"issue":"4","key":"212_CR12","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/s00153-003-0186-y","volume":"43","author":"J. Kraj\u00ed\u010dek","year":"2004","unstructured":"Kraj\u00ed\u010dek J.: Combinatorics of first order structures and propositional proof systems. Arch. Math. Log 43(4), 427\u2013441 (2004)","journal-title":"Arch. Math. Log"},{"issue":"1","key":"212_CR13","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1002\/rsa.3240070103","volume":"7","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"Kraj\u00ed\u010dek J., Pudl\u00e1k P., Woods A.: An exponential lower bound to the size of bounded depth frege proofs of the Pigeonhole principle. Random Struct. Algorithms 7(1), 15\u201339 (1995)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"212_CR14","doi-asserted-by":"crossref","first-page":"649","DOI":"10.2178\/jsl\/1185803628","volume":"72","author":"J. Kraj\u00ed\u010dek","year":"2007","unstructured":"Kraj\u00ed\u010dek J., Skelley A., Thapen N.: NP search problems in low fragments of bounded arithmetic. J. Symbolic Log. 72(2), 649\u2013672 (2007)","journal-title":"J. Symbolic Log."},{"key":"212_CR15","doi-asserted-by":"crossref","unstructured":"Krishnamurthy, B., Moll, R.N.: Examples of hard tautologies in the propositional calculus. In: 13th ACM Symposium on Th. of Computing, pp. 28\u201337 (1981)","DOI":"10.1145\/800076.802454"},{"issue":"4","key":"212_CR16","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1006\/jcss.2002.1830","volume":"64","author":"A. Maciel","year":"2002","unstructured":"Maciel A., Pitassi T., Woods A.: A new proof of the weak pigeonhole principle. J. Comput. Syst. Sci. Arch. 64(4), 843\u2013872 (2002)","journal-title":"J. Comput. Syst. Sci. Arch."},{"key":"212_CR17","volume-title":"Handbook for Mathematical Logic","author":"J. Paris","year":"1977","unstructured":"Paris J., Harrington L. : A mathematical incompleteness in Peano arithmetic. In: Barwise, J. (eds) Handbook for Mathematical Logic, North-Holland, Amsterdam, Netherlands (1977)"},{"key":"212_CR18","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF01200117","volume":"3","author":"T. Pitassi","year":"1993","unstructured":"Pitassi T., Beame P., Impagliazzo R.: Exponential lower bounds for the pigeonhole principle. Comput. complex. 3, 97\u2013308 (1993)","journal-title":"Comput. complex."},{"key":"212_CR19","doi-asserted-by":"crossref","unstructured":"Pudl\u00e1k, P.: Ramsey\u2019s Theorem in bounded arithmetic. In: Proc. Computer Science Logic\u201990, (eds.). E. Borger et.al., LNCS 553, pp.308\u2013317. Springer-Verlag (1991)","DOI":"10.1007\/3-540-54487-9_67"},{"key":"212_CR20","unstructured":"Skelley, A., Thapen, N.: The provably total search problems of bounded arithmetic, submitted (preprint 2008)"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-010-0212-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00153-010-0212-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-010-0212-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T08:23:44Z","timestamp":1559723024000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00153-010-0212-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,12]]},"references-count":20,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["212"],"URL":"https:\/\/doi.org\/10.1007\/s00153-010-0212-9","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"value":"0933-5846","type":"print"},{"value":"1432-0665","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,12]]}}}