caa a22 4500 388039868 CHVBK 20180307125018.0 cr unu---uuuuu 161130e199809 xx s 000 0 eng 10.2307/2586716 doi S0022481200014638 pii (NATIONALLICENCE)cambridge-10.2307/2586716 Forcing on bounded arithmetic II [Elektronische Daten] 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 counting principle. The forcing method on Bounded arithmetic was further developed by P. Beame, J. Krajíček and S. Riis in [4], [7], [6], [8], [5], [12], [11], [13]. It should be noted that J. Krajíček and P. Pudlák 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]. 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 = co-NP problem and P = NP problem. Especially we proved the following theorem and related theorems as Theorems 2, 3 and 4 in Section 2. Theorem. If M[G] is not a model of S2, then NP ≠ co-NP and therefore P ≠ NP. However in the proof of the Theorem, we used a consequence of P = NP. More precisely we used the following as a consequence of NP = co-NP, though it is a consequence of P = NP but not a consequence of NP = co-NP. Suppose that NP = co-NP holds. Then there exists an NP-complete predicate ∃x ≤ t(a) A(x,a) with sharply bounded A(x, a) and a sharply bounded B(y, a) such that ∃x ≤ t(a) A(x,a) ↔ ∀y ≤ s(a)B(y, a). Then there exists polynomial time computable functions f and g such that the following two sequents hold. Copyright © Association for Symbolic Logic 1998 Takeuti Gaisi Department of Mathematics, University of Illinois, Urbana, Illinois 61801, USA E-mail: takeuti@math.uiuc.edu Yasumoto Masahiro Graduate School of Polymathematics, Nagoya University, Chikusa-Ku, Nagoya, 464-01, Japan E-mail: D42985A@nucc.cc.nagoya-u.ac.jp The Journal of Symbolic Logic Cambridge University Press 63/3(1998-09), 860-868 0022-4812 63:3<860 1998 63 JSL https://doi.org/10.2307/2586716 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.2307/2586716 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Takeuti Gaisi Department of Mathematics, University of Illinois, Urbana, Illinois 61801, USA E-mail: takeuti@math.uiuc.edu NATIONALLICENCE 700 1- Yasumoto Masahiro Graduate School of Polymathematics, Nagoya University, Chikusa-Ku, Nagoya, 464-01, Japan E-mail: D42985A@nucc.cc.nagoya-u.ac.jp NATIONALLICENCE 773 0- The Journal of Symbolic Logic Cambridge University Press 63/3(1998-09), 860-868 0022-4812 63:3<860 1998 63 JSL CC0 http://creativecommons.org/publicdomain/zero/1.0 nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-cambridge