{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:52:41Z","timestamp":1759146761650},"reference-count":16,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2004,10,1]],"date-time":"2004-10-01T00:00:00Z","timestamp":1096588800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2004,10]]},"abstract":"Abstract<\/jats:title>We study search problems and reducibilities between them with known or potential relevance to bounded arithmetic theories. Our primary objective is to understand the sets of low complexity consequences (esp. \u03a3b<\/jats:sup>1<\/jats:sub>or \u03a3b<\/jats:sup>2<\/jats:sub>) of theories Si<\/jats:italic><\/jats:sup>2<\/jats:sub>and Ti<\/jats:italic><\/jats:sup>2<\/jats:sub>for a smalli<\/jats:italic>, ideally in a rather strong sense of characterization; or, at least, in the standard sense of axiomatization. We also strive for maximum combinatorial simplicity of the characterizations and axiomatizations, eventually sufficient to prove conjectured separation results. To this end two techniques based on the Herbrand's theorem are developed. They characterize\/axiomatize \u03a3b<\/jats:sup>1<\/jats:sub>\u2010consequences of \u03a3b<\/jats:sup>2<\/jats:sub>\u2010definable search problems, while the method based on the more involved concept of characterization is easier and gives more transparent results. This method yields new proofs of Buss' witnessing theorem and of the relation between PLS and \u03a3b<\/jats:sup>1<\/jats:sub>(T<\/jats:italic>1<\/jats:sup>2<\/jats:sub>), and also an axiomatization of \u03a3b<\/jats:sup>1<\/jats:sub>(T<\/jats:italic>2<\/jats:sup>2<\/jats:sub>). (\u00a9 2004 WILEY\u2010VCH Verlag GmbH & Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200410005","type":"journal-article","created":{"date-parts":[[2004,10,4]],"date-time":"2004-10-04T16:01:01Z","timestamp":1096905661000},"page":"577-586","source":"Crossref","is-referenced-by-count":12,"title":["Herbrandizing search problems in Bounded Arithmetic"],"prefix":"10.1002","volume":"50","author":[{"given":"Ji\u0159\u00ed","family":"Hanika","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2004,10]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"P.Beame S.Cook J.Edmonds R.Impagliazzo andT.Pitassi The relative complexity of NP search problems. Proceedings of the 27th ACM Symposium on Theory of Computing 303\u2013314 (1995).","DOI":"10.1145\/225058.225147"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"J. L.Balc\u00e1zar J.D\u00edaz andJ.Gabarr\u00f3 Structural Complexity (Springer\u2010Verlag Berlin et al. 1988).","DOI":"10.1007\/978-3-642-97062-7"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-69.1.1"},{"key":"e_1_2_1_5_2","unstructured":"S. R.Buss Bounded Arithmetic (Bibliopolis Naples 1986)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.2307\/2586729"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/s001530050118"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00059-C"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"J.Hanika Search Problems and Bounded Arithmetic. PhD thesis Charles University Prague 2004 (Available under http:\/\/www.eccc.uni\u2010trier.de\/eccc\u2010local\/ECCC\u2010Theses\/hanika.html).","DOI":"10.1002\/malq.200410005"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19900360106"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.2307\/2154418"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"J.Kraj\u00ed\u010dek Bounded Arithmetic Propositional Logic and Complexity Theory (Cambridge University Press Cambridge 1995).","DOI":"10.1017\/CBO9780511529948"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(75)90016-X"},{"key":"e_1_2_1_16_2","unstructured":"C. H.Papadimitriou Computational Complexity. Addison\u2010Wesley Publishing Company Reading 1994)."},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"S.Riis Making infinite structures finite in models of second order arithmetic. In: Arithmetic Proof Theory and Computational Complexity (P. Clote and J. Kraj\u00ed\u010dek eds.) pp. 289\u2013319 (Oxford University Press Oxford 1993).","DOI":"10.1093\/oso\/9780198536901.003.0014"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200410005","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200410005","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,14]],"date-time":"2024-01-14T14:00:13Z","timestamp":1705240813000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200410005"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,10]]},"references-count":16,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,10]]}},"alternative-id":["10.1002\/malq.200410005"],"URL":"https:\/\/doi.org\/10.1002\/malq.200410005","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,10]]}}}