Nondeterministic polynomial-time computations and models of arithmetic

ABSTRACT

A semantic, or model theoretic, approach is proposed to study the problems P =? NP and NP =? co-NP. This approach seems to avoid the difficulties that recursion-theoretic approaches appear to face in view of the result of Baker et al. on relativizations of the P =? NP question; moreover, semantical methods are often simpler and more powerful than syntactical ones. The connection between the existence of certain partial extensions of nonstandard models of arithmetic and the question NP =? co-NP is discussed. Several problems are stated about nonstandard models, and a possible link between the Davis-Matijasevi@@@@-Putnam-Robinson theorem on Diophantine sets and the NP =? co-NP question is mentioned.

REFERENCES

• 1: Leonard Max Adleman, Number-theoretic aspects of computational complexity., 1976
• 2: ADLEMAN, t., AND MANDERS, K. Computational complexity of decision procedures for polynomials. In Proceedings of the 16th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1975, pp. 169-177.
• 3: ADLEMAN, L., AND MANDERS, K. Diophanfine complexity. In Proceedings of the 17th Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1976. pp. 81-88.
• 4: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 5: AJTAI, M. ~ }-formulae on finite structures. Ann. Pure AppL Logic 24 (1983), 1-48.
• 6: BAKER, T., GILL, J., AND SOLOVAY, R. Relativizations of the P =? NP question. SlAM J. Comput. 4 (1975), 431-442.
• 7: BARWlSE, J., AND SCHLIPF, J. An introduction to recursively saturated and resplendent models. J. Symb. Logic 41 (1976), 531-536.
• 8: Buss, S. R. Bounded Arithmetic. Bibliopolis, Naples, 1986. (Revision of Ph.D. dissertation, Princeton University, Princeton, N.J. 1985.)
• 9: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 10: DAVIS, M., MATIJASEVIC, Y., AND ROBINSON, J. Hilbert's tenth problem. Diophantine equations: Positive aspects of a negative solution. In Mathematical Developments Arising from Hilberts Problems. F. E. Browder, ed. Proceedings of the Symposium of Pure Mathematics, vol. 28. American Mathematical Society, Providence, R.I., 1976, pp. 323-378.
• 11: Richard A. DeMillo , Richard J. Lipton, The consistency of "P = NP" and related problems with fragments of number theory, Proceedings of the twelfth annual ACM symposium on Theory of computing, p.45-57, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804652]
• 12: FURST, M., SAXE, J. B., AND SIPSER, M. Parity circuits and the polynomial time hierarchy. In Proceedings of the 22nd Annual Symposium on the Foundations of Computer Science. IEEE, New York, 198 I, pp. 262-270.
• 13: GAIFMAN, H. Models and types of Peano's arithmetic. Ann. Math. Logic 9 (1976), 223-306.
• 14: GAIFMAN, H., AND DIMITRACOPOULOS, C. Fragments of Peano's Arithmetic and the MRDP theorem. In Logic and Algorithmic, E. Engeler, H. I_~uchli, and V. Strassen, ed. Monographie No. 30 de L'Enseignement Mathrmatique, Gen~ve, Switzerland, 1982, pp. 187-206.
• 15: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 16: GODEL, K. l}ber formal unentscheidbare S~itze der Principia Mathematica und verwandter Systeme I. Monatshefie fitr Math. und Physik 38 (1931), 173-198.
• 17: GRILLIOT, T.J. Disturbing arithmetic. J. Symb. Logic 50 (1985), 375-379.
• 18: Neil Immerman, Languages which capture complexity classes, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.347-354, December 1983 [doi>10.1145/800061.808765]
• 19: Deborah Joseph , Paul Young, A Survey of Some Recent Results on Computational Complexity in Weak Theories of Arithmetic, Proceedings on Mathematical Foundations of Computer Science, p.46-60, August 31-September 04, 1981
• 20: KANAMORI, A., AND MCALOON, K. G6del incompleteness and finite combinatorics. Ann. Pure Appl. Logic 33 (1987), 23-41.
• 21: KLEENE, S.C. Introduction to Metamathematics. Van Nostrand, New York, 1952.
• 22: KLEENE, S.C. Mathematical Logic. Wiley, New York, 1967.
• 23: KOCHEN, S., AND KRIPKE, S. Non-standard models of Peano Arithmetic. Enseign. Math. 28, 2 (1982), 211-23 I.
• 24: MANDERS, K. L., AND ADLEMAN, L. NP-complete decision problems for binary quadratics. J. Comput. Syst. Sci. 16 (1978), 168-184.
• 25: MATIJASEVII~, Y. Enumerable sets are Diophantine. Dokl. Akad. Nauk SSSR 191 (1970), 279- 282 (Russian). Improved English translation: Soviet Math. Doklady 11 (1970), 354-357.
• 26: MATIJASEVI(2, Y., AND ROaINSON, J. Reduction of an arbitrary diophantine equation to one in 13 unknowns. Acta Arith. 27 (1975), 521-523.
• 27: PARIS, J. B., AND DIMITRACOPOULOS, C. Truth definitions for A0 formulae. In Logic and Algorithmic, E. Engeler, H. L~uchli, and V. Strassen, ed. Monographie No. 30 de L'Enseignement Mathrmatique, Gen~ve, Switzerland, 1982, pp. 317-329.
• 28: PARIS, J. B., AND HARRINGTON, L. A mathematical incompleteness in Peano Arithmetic. In Handbook of Mathematical Logic J. Barwise, ed. North-Holland, Amsterdam, 1977, pp. 1133- 1142.
• 29: PARIS, J. B., AND MILLS, G. Closure properties of countable non-standard integers. Fund. Math. 103 (1979), 205-215.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Relations among complexity classes

General Terms:
Algorithms, Theory