{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T22:38:55Z","timestamp":1697150335346},"reference-count":14,"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":5671,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1998,9]]},"abstract":"Forcing method on Bounded Arithmetic was first introduced by J. B. Paris and A. Wilkie in [10]. Then in [1], [2] and [3], M. Ajtai used the method to get excellent results on the pigeon hole principle and the modulo p<\/jats:italic> counting principle. The forcing method on Bounded arithmetic was further developed by P. Beame, J. Kraj\u00ed\u010dek and S. Riis in [4], [7], [6], [8], [5], [12], [11], [13]. It should be noted that J. Kraj\u00ed\u010dek and P. Pudl\u00e1k used an idea of Boolean valued in [9] and also Boolean valued notion is efficiently used for model theoretic constructions in [7], [6], [8], [5].<\/jats:p>In our previous paper [14], we developed a Boolean valued version of forcing on Bounded Arithmetic using Boolean algebra which is generated by polynomial size circuits from Boolean variables and discussed its relation with NP<\/jats:italic> = co-NP<\/jats:italic> problem and P<\/jats:italic> = NP<\/jats:italic> problem. Especially we proved the following theorem and related theorems as Theorems 2, 3 and 4 in Section 2.<\/jats:p>Theorem<\/jats:sc>. If M[G] is not a model of S2<\/jats:sub>, then NP \u2260 co-NP and therefore P \u2260 NP<\/jats:italic>.<\/jats:p>However in the proof of the Theorem, we used a consequence of P = NP<\/jats:italic>. More precisely we used the following as a consequence of NP<\/jats:italic> = co-NP<\/jats:italic>, though it is a consequence of P<\/jats:italic> = NP<\/jats:italic> but not a consequence of NP<\/jats:italic> = co-NP<\/jats:italic>.<\/jats:p>Suppose that NP = co-NP holds. Then there exists an NP-complete predicate \u2203x \u2264 t(a) A(x,a) with sharply bounded A(x, a) and a sharply bounded B(y, a) such that \u2203x \u2264 t(a) A(x,a) \u2194 \u2200y \u2264 s(a)B(y, a). Then there exists polynomial time computable functions f and g such that the following two sequents hold<\/jats:italic>.<\/jats:p>","DOI":"10.2307\/2586716","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T14:01:28Z","timestamp":1146924088000},"page":"860-868","source":"Crossref","is-referenced-by-count":3,"title":["Forcing on bounded arithmetic II"],"prefix":"10.1017","volume":"63","author":[{"given":"Gaisi","family":"Takeuti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masahiro","family":"Yasumoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200014638_ref002","first-page":"1","volume-title":"Feasible mathematics","author":"Ajtai","year":"1990"},{"key":"S0022481200014638_ref001","first-page":"346","volume-title":"Proceedings of the IEEE 29th annual symposium on foundation of computer science","author":"Ajtai","year":"1988"},{"key":"S0022481200014638_ref010","first-page":"317","volume-title":"Counting problems in bounded arithmetic","author":"Paris","year":"1985"},{"key":"S0022481200014638_ref012","unstructured":"Rus S. , Independence in bounded arithmetic, Ph.D. thesis , Oxford University, 1993."},{"key":"S0022481200014638_ref014","first-page":"120","volume-title":"G\u00f6del '96","author":"Takeuti","year":"1996"},{"key":"S0022481200014638_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-017-0487-8_4"},{"key":"S0022481200014638_ref003","first-page":"402","volume-title":"Proceedings of the 26th annual ACM symposium on theory of computing","author":"Ajtai","year":"1994"},{"key":"S0022481200014638_ref011","first-page":"289","volume-title":"Arithmetic, proof theory, and computational complexity","author":"Rus"},{"key":"S0022481200014638_ref009","first-page":"193","volume-title":"Propositional provability and models of weak arithmetic","author":"Kraj\u00ed\u010dek","year":"1990"},{"key":"S0022481200014638_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-2566-9_10"},{"key":"S0022481200014638_ref013","volume-title":"Technical Report RS 94-21","author":"Rus","year":"1994"},{"key":"S0022481200014638_ref004","unstructured":"Beame P. and Rus S. , More on the relative strength of counting principles, to appear in DIMACS."},{"key":"S0022481200014638_ref005","volume-title":"Proceedings of logic colloquium 1995, Haifa","author":"Kraj\u00ed\u010dek"},{"key":"S0022481200014638_ref006","volume-title":"Encyclopedia of mathematics and its application","volume":"60","author":"Kraj\u00ed\u010dek","year":"1995"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200014638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,10]],"date-time":"2019-05-10T16:21:35Z","timestamp":1557505295000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200014638\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,9]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,9]]}},"alternative-id":["S0022481200014638"],"URL":"https:\/\/doi.org\/10.2307\/2586716","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,9]]}}}