NP-COMPLETE NUMBER-THEORETIC PROBLEM

Systems of nonlinear equations of the form [formula omitted], where A is an m × n matrix of ratmnal constants and [formula omitted] are column vectors, are considered Each [formula omitted] is of the form [formula omitted] 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 [formula omitted] 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 [formula omitted] 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. © 1979, ACM. All rights reserved.