Let a problem instance be given as $(\phi(x_1,x_2,\dots, x_J),M)$ where $\phi$ is a diophantine equation, $J\leq 9$, and $M$ is a natural number. The decision problem is whether or not a given instance has a solution in natural numbers such that $\sum_{j=1}^J x_j \leq M$. With no upper bound M, the problem is undecidable (if I have the literature correct). With the bound, what is the computational complexity? If the equation does have such a solution, then the solution itself serves as a polytime certificate, putting it in NP. What else can be said about the complexity of this problem?
|
|
A particular quadratic Diophantine equation is NP-complete. $R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY - c = 0$ is NP-complete. ($a$, $b$, and $c$ are given in their binary representations. $a$, $b$, $c$, $X$, and $Y$ are positive integers). Note that there are trivial bounds on the sizes of $X$ and $Y$ in terms of $a$, $b$, and $c$. Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Quadratic Polynomials. STOC 1976: 23-29 |
|||||||||||||
|
|
Seems to me that you could encode SAT in the usual polynomial manner, with variables restricted to being 0 or 1. |
|||||||||||||||||
|
