An NP-Complete Number-Theoretic Problem
Eitan M. Gurari, Óscar H. Ibarra · Journal of the ACM · 1979
Systems of nonlinear equations of the form D Aft = ~(x), where A is an m × n matrix of ratmnal constants and fi = (yl, , y.), 8(x) = (ol(x), , on(x)) are column vectors, are considered Each o,(x) is of the form r,(x) or lr,(x)], where r,(x) is a rational function ofx with raUonal coefficients It Is shown that the problem of determining for a given system D whether there exists a nonnegatlve integral solution (yh,, y., x) satisfying Dts deodable In fact, the problem is NP-complete when restricted to systems D m which the maximum degree of the polynomials defining the o,(x)'s is bounded by some fixed polynomial m the length of the representation of D Some recent results connecting Dmphantme equations and counter machines are briefly mentioned.KEY WORDS AND PHRASES Hdbert's tenth problem, nonhnear integer programming, Dlophantme equation, decldabthty, NP-complete, polynomial time-bounded Turmg machine, counter machine CR CATEGORIES 5 23, 5 25, 5 26, 5 27, 5 41 lntroducttonHilbert's tenth problem [7] is the problem of determining for a given polynomial p(xl ..... xn) (or a system of polynomials p,(xl .... xn), 1 _< i _< m) with integer coefficients whether it has a nonnegatlve integer solution, i.e., nonnegatlve integers cq, ..., an such that p(al ..... an) = 0 (p,(a~ ..... an) = 0 for 1 _< t _< m).Hilbert's tenth problem is undecidable for (i) (iI) polynomials of degree 4 [14, 18], polynomials in t3 unknowns [15] (it was reported m [13] that this has been reduced to 9 unknowns), and (iii) systems of quadratic polynomials [3,9].On the other hand, Hilbert's tenth problem is decidable for (iv) polynomials in 1 unknown and (v) polynomials of degree 2 [17].It is not known whether the degree 4 in (i) and the 9 unknowns in (ii) are minimal.Also, the minimal number of quadratic polynomials needed to prove the undecidability in (iii) is not known.A decision procedure for a large class of polynomials in 2 unknowns is known [3] but not yet for the general case.For 3 unknowns almost nothing is known.Pinpointing the precise boundary between decidability and undecidability of Hilbert's tenth problem with respect to the degree, the number of unknowns, and number of quadratic polynomials in the system remains an interesting research problem.A related problem which is of practical interest is that of finding special classes of polynommls (or systems of polynomials) for which Hilbert's tenth problem is decidable This paper studies one such class.Consider a system of nonhnear equations of the form D: Aft = ~(x), where A is an m X n matrix of rational constants and fi = (yl ..... yn), ~(x) = (ol(x) ..... o,~(x)) are column