An NP-complete number-theoretic problem

ABSTRACT

Systems of nonlinear equations of the form D: Ay = σ.(x), where A is an m×n matrix of rational constants and y = (Y₁,...,y_n), σ(x) = (σ₁(x),..., σ_m (x)) are column vectors are considered. Each σ_i(x) is of the form r_i(x) or @@@@r_i(x)@@@@, where r_i(x) is a rational function of x with rational coefficients. It is shown that the problem of determining for a given system D whether there exists a nonnegative integral solution (y₁,...,y_n,X) satisfying D is decidable. In fact, the problem is NP-complete when restricted to systems D in which the maximum degree of the polynomials defining the σ_i(x)'s is bounded by some fixed polynomial in the length of the representation of D. Some recent results connecting Diophantine equations and counter machines are briefly mentioned.

References

1. 1.Borosh, I. and Treybig, L. B., Bounds on positive integral solutions of linear Diophantine equations, Proceedings of the American Mathematical Society, vol. 55 (1976), 299-304.
2. 2.Cook, S. A., The complexity of theorem proving procedures, Conference Record of the Third ACM Symposium on Theory of Computing(1971), 151-158.
3. 3.Davis, M., Matijasevič, Y. and Robinson, J., Hilbert's tenth problem. Diophantine equations: positive aspects of a negative solution. Proceedings of Symposia in Pure Mathematics,vol. 28 (1976), 323-378.
4. 4.Garfinkel, R. S. and Nemhauser, G. L., "Integer Programming," John Wiley, New York, 1972.
5. 5.Gurari, E. and Ibarra, O. H., Two-way counter machines and Diophantine equations, in preparation.
6. 6.Gurari, E. and Ibarra, O. H., A decidable class of counter machines with applications to some number-theoretic problems, CSci Technical Report No. 77-10, University of Minnesota(submitted for publication).
7. 7.Hilbert, D., Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker-Kongrass zu Paris 1900, Nachr. Akad. Wiss. Göttingen Math.-Phys. (1900), 253-297; Translation: Bull. Am. Math. Soc., 8 (1901-1902), 437-479.
8. 8.Ibarra, O. H., Reversal-bounded multicounter machines and their decision problems, Journal of the Association for Computing Machinery, vol. 25 (1978), 116-133.
9. 9.Jeroslow, R. G., There cannot be any algorithm for integer programming with quadratic constraints, Operations Research, vol. 21 (1973), 221-224.
10. 10.Karp, R. M. Reducibility among combinatorial problems, inComplexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds., Plenum Press, New York, (1972), 85-104.
11. 11.Liu, L. and Weiner, P., A characterization of semilinear sets, Journal of Computer and System Sciences, vol. 4 (1970), 299-307.
12. 12.Luenberger, D. G.,."Introduction to Linear and Nonlinear Programming," Addison-Wesley, Reading, Mass., 1973.
13. 13.Manders, K., and Adleman, L., NP-complete decision problems for quadratic polynomials, Conference Record of the Eighth ACM Symposium on Theory of Computing,(1976), 23-29.
14. 14.Matijasevič, Y., Enumerable sets are Diophantine (Russian), Dokl. Akad. Nauk SSSR, 191 (1970), 279-282.
15. 15.Matijasevič, Y. and Robinson, J., Reduction of an arbitrary Diophantine equation to one in 13 Unknowns, Acta Arithmetica, 27 (1975), 521-553.
16. 16.Sahni, S., Computationally related problems. SIAM Journal on Computing, vol. 3 (1974), 262-279.
17. 17.Siegel, C., Zur theorie de quadratischen formen Nachr. Akad. Wiss. Göttingen Math.-Phys. K1. II (1972), 21-46.
18. 18.Skolem, T., Diophatische gleichungen, Ergebisse d. Math. u. Ihrer Grenzgebiete, Bd. 5, Julius Springer, 1938.

Index Terms

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Number-theoretic computations

• Theory of computation

  • Computational complexity and cryptography

    • Problems, reductions and completeness