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?



Is the solution bounded Diophantine problem NP-complete? 
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


