{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T04:04:53Z","timestamp":1679544293624},"reference-count":9,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":8228,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1991,9]]},"abstract":"<jats:p>In [1] S. Buss introduced systems of bounded arithmetic <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline1.png\" \/>, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline2.png\" \/>, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline3.png\" \/>, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline4.png\" \/> (<jats:italic>i<\/jats:italic> = 1, 2, 3, \u2026). <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline1.png\" \/> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline2.png\" \/> are first order systems and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline3.png\" \/> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline4.png\" \/> are second order systems. <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline1.png\" \/> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline2.png\" \/> are closely related to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline5.png\" \/> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline6.png\" \/> respectively in the polynomial hierarchy, and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline3.png\" \/> and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline4.png\" \/> are closely related to PSPACE and EXPTIME respectively. One of the most important problems in bounded arithmetic is whether the hierarchy of bounded arithmetic collapses, i.e. whether <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline7.png\" \/> = <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline2.png\" \/> or <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline2.png\" \/> = <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline1.png\" \/> for some <jats:italic>i<\/jats:italic>, or whether <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline4.png\" \/> = <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline3.png\" \/>, or whether <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline3.png\" \/> is a conservative extension of <jats:italic>S<\/jats:italic><jats:sub>2<\/jats:sub> = \u22c3<jats:sub><jats:italic>i<\/jats:italic><\/jats:sub><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline1.png\" \/>. These problems are relevant to the problems whether the polynomial hierarchy PH collapses or whether PSPACE = PH or whether PSPACE = EXPTIME. It was shown in [4] that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline2.png\" \/> = <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline7.png\" \/> implies <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0022481200024191_inline8.png\" \/> and consequently the collapse of the polynomial hierarchy. We believe that the separation problems of bounded arithmetic and the separation problems of computational complexities are essentially the same problem, and the solution of one of them will lead to the solution of the other.<\/jats:p>","DOI":"10.2307\/2275071","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:41:03Z","timestamp":1146955263000},"page":"1038-1063","source":"Crossref","is-referenced-by-count":2,"title":["A second order version of <i>S<\/i><sub>2<\/sub><sup><i>i<\/i><\/sup> and <i>U<\/i><sub>2<\/sub><sup>1<\/sup>"],"prefix":"10.1017","volume":"56","author":[{"given":"Gaisi","family":"Takeuti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200024191_ref008","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/106\/1057828"},{"key":"S0022481200024191_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(88)90046-2"},{"key":"S0022481200024191_ref005","volume-title":"The complexity of computing","author":"Savage","year":"1976"},{"key":"S0022481200024191_ref003","unstructured":"Clote P. and Takeuti G. , Bounded arithmetic for NC, AlogTime, L and NL, Manuscripts, 1989."},{"key":"S0022481200024191_ref002","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/106\/1057816"},{"key":"S0022481200024191_ref001","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200024191_ref004","volume-title":"Annals of Pure and Applied Logic","author":"Kraj\u00ed\u010dek"},{"key":"S0022481200024191_ref006","volume-title":"Proof theory","author":"Takeuti","year":"1980"},{"key":"S0022481200024191_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF01621092"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200024191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T10:34:55Z","timestamp":1679481295000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200024191\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":9,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["S0022481200024191"],"URL":"https:\/\/doi.org\/10.2307\/2275071","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}