{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,20]],"date-time":"2024-09-20T15:54:50Z","timestamp":1726847690362},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Math. Log."],"published-print":{"date-parts":[[2009,6]]},"abstract":"<jats:p> The complexity class of [Formula: see text]-polynomial local search (PLS) problems is introduced and is used to give new witnessing theorems for fragments of bounded arithmetic. For 1 \u2264 i \u2264 k + 1, the [Formula: see text]-definable functions of [Formula: see text] are characterized in terms of [Formula: see text]-PLS problems. These [Formula: see text]-PLS problems can be defined in a weak base theory such as [Formula: see text], and proved to be total in [Formula: see text]. Furthermore, the [Formula: see text]-PLS definitions can be skolemized with simple polynomial time functions, and the witnessing theorem itself can be formalized, and skolemized, in a weak base theory. We introduce a new [Formula: see text]-principle that is conjectured to separate [Formula: see text] and [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0219061309000847","type":"journal-article","created":{"date-parts":[[2010,7,15]],"date-time":"2010-07-15T08:16:53Z","timestamp":1279181813000},"page":"103-138","source":"Crossref","is-referenced-by-count":11,"title":["POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC"],"prefix":"10.1142","volume":"09","author":[{"given":"ARNOLD","family":"BECKMANN","sequence":"first","affiliation":[{"name":"Department of Computer Science, Swansea University, Swansea SA2 8PP, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SAMUEL R.","family":"BUSS","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of California, San Diego, La Jolla, CA 92093-0112, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2009.06.004"},{"key":"rf2","series-title":"Ontos Series on Mathematical Logic","author":"Beckmann A.","year":"2010"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2005.05.002"},{"key":"rf5","series-title":"Contemporary Mathematics","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1090\/conm\/106\/1057816","volume":"106","author":"Buss S. R.","year":"1990"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)00057-A"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(98)80016-5"},{"key":"rf8","first-page":"1","volume":"69","author":"Buss S. R.","journal-title":"Proc. London Math. Soc."},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1185803628"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1993-1124169-X"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511529948"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19900360106"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90043-L"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.2307\/2269958"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075316"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(99)00008-1"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1230396927"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.2307\/2275794"}],"container-title":["Journal of Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219061309000847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T04:29:49Z","timestamp":1565152189000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219061309000847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,6]]},"references-count":18,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2009,6]]}},"alternative-id":["10.1142\/S0219061309000847"],"URL":"https:\/\/doi.org\/10.1142\/s0219061309000847","relation":{},"ISSN":["0219-0613","1793-6691"],"issn-type":[{"value":"0219-0613","type":"print"},{"value":"1793-6691","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,6]]}}}