The consistency of "P = NP" and related problems with fragments of number theory

ABSTRACT

The main results of this paper demonstrate the consistency of “P &equil; NP” and a variant of “NP @@@@ coNP” with certain natural fragments of number theory to be defined precisely in the sequel.@@@@ Consistency results represent an approach to the lower bound problems of complexity theory which points to a number of interesting lines of inquiry. Our ultimate goal is to make precise the difficulty of proving certain nontrivial lower bounds. Among the possibilities which follow from this approach are: (1) that logical techniques may help us resolve the P &equil; NP question, (2) that showing why certain arguments must fail may lead to mathematical tools capable of resolving the problems, and (3) that the special character of model theoretic methods in complexity theory may lead to new results which are of purely logical interest. We will address these possibilities below.

REFERENCES

• 1: Richard A. DeMillo , Richard J. Lipton, Some connections between mathematical logic and complexity theory, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.153-159, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804408]
• 2: J. Barwise, editor, Handbook of Mathematical Logic, North-Holland, 1978.
• 3: J. Paris and L. Harrington, “A Mathematical Incompleteness in Peano Arithmetic”, in {2}, pp. 1132–1142.
• 4: J. Hartmanis , J. E. Hopcroft, Independence results in computer science, ACM SIGACT News, v.8 n.4, p.13-24, October-December 1976 [doi>10.1145/1008335.1008336]
• 5: J. Hartmanis, Feasible Computation, SIAM, 1978.
• 6: R. Lipton, “Model Theoretic Aspects of Computational Complexity”, Proceedings 19th FOCS, 1978, pp. 193–200.
• 7: L.G. Khachiyan, “A Polynomial Algorithm for Linear Programming” (in Russian) Doklady Akad. Nauk USSR, Vol. 244, No. 5, 1979, pp. 1093–1096.
• 8: Th. Skolem, “Uber die Nich-charakterisier barkeit der Zahlenreihe Mittels endlich oder abzahlbar unendlich vieler Aussagen mit Ausschliesslich Zahlenveriablen”, Fund. Math. 23, 1934, pp. 150–161.
• 9: D.S. Scott, “On Constructing Models for Arithmetic”, Infinitistic Methods, Warsaw, 1959 (Oxford, 1961), pp. 235–255.
• 10: Stephen A. Cook, Feasibly constructive proofs and the propositional calculus (Preliminary Version), Proceedings of seventh annual ACM symposium on Theory of computing, p.83-97, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803756]
• 11: S. Kleene, Introduction to Metamathematics, VanNostrand, 1953.
• 12: R. Statman, “Herbrand's Theorem and Gentzen's Notion of Direct Proof”, in {2}, pp. 897–912.
• 13: R. Statman, “Lower Bounds on Herbrand's Theorem”, Proceedings of the American Mathematical Society, Vol. 15, No. 1 , June, 1979, pp. 104–107.
• 14: A. Meyer and L. Stockmeyer, “Nonelementary Word Problems in Automata Theory and Logic”, Proceedings AMS Symposium on Complexity of Computation, 1973.
• 15: V. Pratt, “Every Prime Has a Succinct Certificate”, SIAM J. Computing, 1975.
• 16: D. Dobkin and S. Reiss, “The Complexity of Linear Programming”, Yale University Technical Report, No. 69, June 1978.
• 17: J.P. Burgess, “Forcing”, in {2}, pp. 403–542.
• 18: Th. Skolem, “Peano's Axioms and Models of Arithmetic”, Mathematical Interpretations of Formal Systems, Amsterdam, 1955, pp. 1–14.
• 19: A.Fraenkel, Abstract Set Theory, North-Holland, 1976.
• 20: J. Bell and M. Machoyer, A Course in Mathematical Logic, North-Holland, 1976.
• 21: J. Shepherdson, “Nonstandard Models of Fragments of Arithmetic”, Model Theory, (J.Addison, ed.), North-Holland, 1963, pp. 342–358.
• 22: P.J. Cohen, Set Theory and the Continuum Hypothesis, Benjamin, 1966.
• 23: A. Ehrenfeucht and G. Kreisel, “Strong Models of Arithmetic”, Mathematics and Logic, 1966.
• 24: G.H. Hardy, “Properties at Logarithmico-Exponential Functions,” Proceedings of the London Mathematical Society, 1912, Vol. 2, No. 10, pp. 54–90.
• 25: W. Wheeler and J. Hirschfeld, Forcing, Arithmetic and Division Rings, Springer Lecture Notes in Mathematics #454, 1975.
• 26: J. Bell and J. Slomson, Models and Ultra-products, North-Holland, 1970.
• 27: A. Robinson, Nonstandard Arithmetic and Generic Arithmetic, Proceedings 4th International Congress on Logic, Methodology and Philosophy of Science, 1971, North-Holland, 1973, pp. 137–154.
• 28: T. Baker, J.Gill and R. Solovay, “Relativiations of the P&equil;?NP Question.”, SIAM Journal of Computing 4 (Dec. 1975), pp. 431–432.
• 29: Michael O'Donnell, A programming language theorem which is independent of Peano Arithmetic, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.176-188, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804411]
• 30: A. Robinson, “Forcing in Model Theory”, Symposia Mathematica, Vol. 5, 1971, pp. 69–82.
• 31: M.E. Szabo, editor, The Collected Papers of Gerhard Gentzen, North-Holland, 1969.
• 32: J. Paris, “Some Independence Results for Peano Arithmetic”, Journal of Symbolic Logic, 1978.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory