An NP-Complete Number-Theoretic Problem

Abstract

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.