Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-16T16:13:57.505Z Has data issue: false hasContentIssue false
  • English
  • Français

Forcing on bounded arithmetic II

Published online by Cambridge University Press:  12 March 2014

Gaisi Takeuti  and
Masahiro Yasumoto
Gaisi Takeuti
Affiliation:
Department of Mathematics, University of Illinois, Urbana, Illinois 61801, USA E-mail: [email protected]
Masahiro Yasumoto
Affiliation:
Graduate School of Polymathematics, Nagoya University, Chikusa-Ku, Nagoya, 464-01, Japan E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 63 , Issue 3 , September 1998 , pp. 860 - 868
Copyright
Copyright © Association for Symbolic Logic 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Ajtai, M., The complexity of the pigeon hole principle, Proceedings of the IEEE 29th annual symposium on foundation of computer science, 1988, pp. 346–355.Google Scholar
[2]Ajtai, M., Parity and the pigeon hole principle, Feasible mathematics (Buss, S. R. and Scott, P. J., editors), Birkhauser, 1990, pp. 1–24.Google Scholar
[3]Ajtai, M., The independence of the modulo p counting principles, Proceedings of the 26th annual ACM symposium on theory of computing, ACM Press, 1994, pp. 402–417.Google Scholar
[4]Beame, P. and Rus, S., More on the relative strength of counting principles, to appear in DIMACS.Google Scholar
[5]Krajíček, J., Extensions of models of PV, Proceedings of logic colloquium 1995, Haifa (Harnik, V. and Makowski, J., editors), Springer-Verlag.Google Scholar
[6]Krajíček, J., Bounded arithmetic, propositional logic and complexity theory, Encyclopedia of mathematics and its application, vol. 60, Cambridge University Press, Cambridge-New York-Melbourne, 1995.Google Scholar
[7]Krajíček, J., On Frege and extended Frege proof systems, Feasible mathematics II (Clote, P. and Remmel, J. B., editors), Birkhäuser, 1995, pp. 284–319.CrossRefGoogle Scholar
[8]Krajíček, J., On method for proving lower bounds in propositional logic, Logic and scientific method (Chiara, M. L. Dallaet al., editors), Kluwer Academic Publishers, Dordrechet, 1997, pp. 69–83.CrossRefGoogle Scholar
[9]Krajíček, J. and Pudlák, P., Propositional provability and models of weak arithmetic, Lecture Notes in Computer Science, no. 440, 1990, pp. 193–210.Google Scholar
[10]Paris, J. B. and Wilkie, A., Counting problems in bounded arithmetic, Lecture Notes in Mathematics, Methods in Mathematical Logic, no. 1130, 1985, pp. 317–340.Google Scholar
[11]Rus, S., Making infinite structures finite in models of second order bounded arithmetic, Arithmetic, proof theory, and computational complexity (Clote, P. and Krajíček, J., editors), Oxford University Press, pp. 289–319.Google Scholar
[12]Rus, S., Independence in bounded arithmetic, Ph.D. thesis, Oxford University, 1993.Google Scholar
[13]Rus, S., Count(q) does not imply Count(p), Technical Report RS 94-21, BRICS, 1994.Google Scholar
[14]Takeuti, G. and Yasumoto, M., Forcing on bounded arithmetic, Gödel '96 (Hajek, P., editor), Lecture Notes in Logic, no. 6, 1996, pp. 120–138.Google Scholar