{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T16:46:08Z","timestamp":1649004368711},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":6951,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1995,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we characterize the well-known computational complexity classes of the polynomial time hierarchy as classes of provably recursive functions (with graphs of suitable bounded complexity) of some second order theories with weak comprehension axiom schemas but without any induction schemas (Theorem 6). We also find a natural relationship between our theories and the theories of bounded arithmetic <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200018910_inline1\" \/> (Lemmas 4 and 5). Our proofs use a technique which enables us to \u201cspeed up\u201d induction without increasing the bounded complexity of the induction formulas. This technique is also used to obtain an interpretability result for the theories of bounded arithmetic <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200018910_inline1\" \/> (Theorem 4).<\/jats:p>","DOI":"10.2307\/2275511","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:54:10Z","timestamp":1146956050000},"page":"103-121","source":"Crossref","is-referenced-by-count":1,"title":["Delineating classes of computational complexity via second order theories with weak set existence principles. I"],"prefix":"10.1017","volume":"60","author":[{"given":"Aleksandar","family":"Ignjatovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200018910_ref013","unstructured":"Solovay Robert , Letter to P. H\u00e1jek, August 1976."},{"key":"S0022481200018910_ref009","unstructured":"Ignjatovi\u0107 Aleksandar , Induction in theories of bounded arithmetic, manuscript in preparation."},{"key":"S0022481200018910_ref008","volume-title":"Delineating classes of computational complexity via second order theories with weak set existence principles","author":"Ignjatovi\u0107","year":"1991"},{"key":"S0022481200018910_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-3466-1_9"},{"key":"S0022481200018910_ref010","unstructured":"Ignjatovi\u0107 Aleksandar and Sieg Wilfried , Herbrand analysis of some theories with weak set existence principles, manuscript in preparation."},{"key":"S0022481200018910_ref012","doi-asserted-by":"publisher","DOI":"10.4064\/fm-136-2-85-89"},{"key":"S0022481200018910_ref005","unstructured":"Ferreira Fernando J. I. , Polynomial time computable arithmetic and conservative extensions, Ph.D. thesis, Penn-sylvania State University, University Park, Pennsylvania, 1988."},{"key":"S0022481200018910_ref004","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/106\/1057819"},{"key":"S0022481200018910_ref003","first-page":"83","volume-title":"Proceedings of the Seventh Annual ACM Symposium on Theory of Computing","author":"Cook","year":"1975"},{"key":"S0022481200018910_ref001","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200018910_ref007","volume-title":"Metamathematics of first-order arithmetic","author":"H\u00e1jek","year":"1992"},{"key":"S0022481200018910_ref002","volume-title":"Unprovability of consistency statements in fragments of bounded arithmetic","author":"Buss","year":"1994"},{"key":"S0022481200018910_ref011","unstructured":"Leivant Daniel , A foundational delineation of computational feasibility, draft (07 1991)."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200018910","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T19:31:21Z","timestamp":1557862281000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200018910\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["S0022481200018910"],"URL":"https:\/\/doi.org\/10.2307\/2275511","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,3]]}}}