{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:47:30Z","timestamp":1781077650908,"version":"3.54.1"},"reference-count":27,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":2476,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2007,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We give combinatorial and computational characterizations of the NP search problems definable in the bounded arithmetic theories <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005405_inline01\"\/> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200005405_inline02\"\/>.<\/jats:p>","DOI":"10.2178\/jsl\/1185803628","type":"journal-article","created":{"date-parts":[[2007,12,19]],"date-time":"2007-12-19T16:24:48Z","timestamp":1198081488000},"page":"649-672","source":"Crossref","is-referenced-by-count":23,"title":["NP search problems in low fragments of bounded arithmetic"],"prefix":"10.1017","volume":"72","author":[{"given":"Jan","family":"Kraj\u00ed\u010dek","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alan","family":"Skelley","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Neil","family":"Thapen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200005405_ref026","first-page":"308\u2013312","volume-title":"Proceedings of Computer Science Logic","volume":"553","author":"Pudl\u00e1k","year":"1992"},{"key":"S0022481200005405_ref025","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200117"},{"key":"S0022481200005405_ref023","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075316"},{"key":"S0022481200005405_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"S0022481200005405_ref021","first-page":"229\u2013234","volume-title":"20th annual ACM symposium on the Theory of Computing","author":"Papadimitriou","year":"1988"},{"key":"S0022481200005405_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531024"},{"key":"S0022481200005405_ref016","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240070103"},{"key":"S0022481200005405_ref015","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19900360106"},{"key":"S0022481200005405_ref014","doi-asserted-by":"publisher","DOI":"10.4064\/fm170-1-8"},{"key":"S0022481200005405_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"S0022481200005405_ref010","first-page":"375\u2013377","article-title":"A note on conservativity relations among bounded arithmetic theories","volume":"48","author":"Impagliazzo","year":"2002","journal-title":"Mathematical Logic Quaterly"},{"key":"S0022481200005405_ref009","unstructured":"Hanika J. , Search problems and bounded arithmetic, Ph.D. thesis, Charles University, Prague, 2004, Available via the ECCC (http:\/\/eccc.hpi-web.de\/eccc)."},{"key":"S0022481200005405_ref005","doi-asserted-by":"publisher","DOI":"10.1007\/s001530050118"},{"key":"S0022481200005405_ref004","first-page":"1095\u20131115","volume":"63","author":"Chiari","year":"1998","journal-title":"Witnessing functions in bounded arithmetic and search problems"},{"key":"S0022481200005405_ref003","first-page":"1\u201321","article-title":"An application of Boolean complexity to separation problems in bounded arithmetic","volume":"69","author":"Buss","year":"1994","journal-title":"Proceedings of the London Mathematical Society"},{"key":"S0022481200005405_ref002","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200005405_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00059-C"},{"key":"S0022481200005405_ref024","first-page":"1235\u20131244","volume":"53","author":"Paris","year":"1988","journal-title":"Provability of the pigeonhole principle and the existence of infinitely many primes"},{"key":"S0022481200005405_ref018","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1830"},{"key":"S0022481200005405_ref020","first-page":"794\u2013801","article-title":"On graph-theoretic lemmata and complexity classes (extended abstract)","volume":"II","author":"Papadimitriou","year":"1990","journal-title":"Proceedings of the 31st IEEE symposium on Foundations of Computer Science"},{"key":"S0022481200005405_ref001","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1575"},{"key":"S0022481200005405_ref012","unstructured":"Kraj\u00ed\u010dek Jan ,."},{"key":"S0022481200005405_ref013","first-page":"73\u201386","volume":"59","author":"Kraj\u00ed\u010dek","year":"1994","journal-title":"Lower bounds to the size of constant-depth propositional proofs"},{"key":"S0022481200005405_ref006","first-page":"83\u201397","volume-title":"Conference record of seventh annual ACM symposium on theory of computing","author":"Cook","year":"1975"},{"key":"S0022481200005405_ref027","unstructured":"Pudl\u00e1k Pavel , On \u03a31 sentences in bounded arithmetic, In preparation."},{"key":"S0022481200005405_ref019","unstructured":"Morioka Tsuyoshi , Logical approaches to the complexity of search problems: Proof complexity, quantified propositional calculus, and bounded arithmetic, Ph.D. thesis, University of Toronto, 2005, Available via the ECCC (http:\/\/eccc.hpi-web.de\/eccc)."},{"key":"S0022481200005405_ref008","doi-asserted-by":"publisher","DOI":"10.1002\/malq.200410005"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200005405","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T22:12:49Z","timestamp":1556748769000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200005405\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,6]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2007,6]]}},"alternative-id":["S0022481200005405"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1185803628","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,6]]}}}