NP-complete decision problems for quadratic polynomials

ABSTRACT

In this article we show the NP-completeness of some simple number-theoretic problems. Natural simplifications of these problems invariably are known to be in P. Our research was motivated by the question whether one could study non-deterministic computation without loss of generality on a restricted, number theoretically significant class of nondeterministic Turing machines, the nondeterministic diophantine machines defined below [1,2]. The results suggest this is true. Because of the relative difficulty of the reduction of the satisfiability problem used in the proof, and the distinctly number-theoretic character of the problems shown to be NP-complete, we hope that the NP-completeness of these problems will play a role in showing the NP-completeness of further problems of a numerical nature, much as the satisfiability problem has in showing the NP-completeness of combinatorial problems ([3],[5]). The results illustrate an intimate connection between problems in computational theory, such as “P&equil;NP?”, and problems in number theory, e.g. about quadratic congruences in one unknown, which are just beyond the range in which efficient algorithms exist. Thus our work exposes an interface between the state-of-the-art in number theory and in the theory of computation. Also, our results can be seen as the solution to a natural and important revision of Hilbert's 10thproblem: Give a feasible algorithmic procedure to decide whether an arbitrary diophantine equation has solutions. Unless P&equil;NP this is impossible, even for a class of quadratic diophantine equations in two unknowns for which a decision procedure in the original sense is in fact available. Certainly, these results present a striking rigorous demonstration that number theorists' intuitions about where problems about diophantine equations and quadratic congruences start to be truly difficult are justified.

REFERENCES

• 1: Adleman, L. and Manders, K., "Computational Complexity of Decision Procedures for Polynomials," 16th Annual Symposium on Foundations of Computer Science (Oct. 1975), 169-177.
• 2: Adleman, L. and Manders, K., "Number-theoretic Aspects of Computational Complexity." In preparation.
• 3: 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]
• 4: Gill, J., "Axiomatic Independence of the Question NP&equil;P?." To appear.
• 5: Karp, R.M., "Reducibility Among Combinatorial Problems," in Complexity of Computer Computation, eds. R.N. Miller and J.W. Thatcher, Plenum Press, 1972, pp. 85-104.
• 6: Richard E. Ladner, On the Structure of Polynomial Time Reducibility, Journal of the ACM (JACM), v.22 n.1, p.155-171, Jan. 1975 [doi>10.1145/321864.321877]
• 7: Matijasevič, Y., "Enumerable Sets are Diophantine (Russian)," Dokl. Acad. Nauk SSSR 191 (1970), 279-282.
• 8: Matijasevič, Y. and Robinson, J., "Reduction of an Arbitrary Diophantine Equation to One in 13 Unknowns," Acta Arithmetica 27 (1975), 521-553.
• 9: Matijasevič, Y. Private communication.
• 10: Gary L. Miller, Riemann's Hypothesis and tests for primality, Proceedings of seventh annual ACM symposium on Theory of computing, p.234-239, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803773]
• 11: Miller, G.L. Ph.D. Thesis, Berkeley, 1975.
• 12: Niven, I. and Zuckerman, H. An Introduction to the Theory of Numbers, John Wiley and Sons, Inc. (1972).
• 13: Pratt, V., "Succinct Certificates for the Primes." To appear.
• 14: Sato, D. Private communication.

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); Computations on polynomials

General Terms:
Theory