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?

$\begingroup$ @R Hahn: As Diophantine Mathematician answered, the problem in the revised (v2) question is NPcomplete. $\endgroup$ – Tsuyoshi Ito Aug 23 '10 at 11:54
A particular quadratic Diophantine equation is NPcomplete.
$R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY  c = 0$
is NPcomplete. ($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: NPComplete Decision Problems for Quadratic Polynomials. STOC 1976: 2329

$\begingroup$ Thank you. I have edited the problem to make it more precise. $\endgroup$ – R Hahn Aug 23 '10 at 5:21

$\begingroup$ What about the subproblem for $a=1$? $R(b,c) \Leftrightarrow \exists X \exists Y :X^2 + bY  c = 0$ $\endgroup$ – user22042 Mar 28 '12 at 15:12

$\begingroup$ And the answer to this question is that it is also NPcomplete. The problem with general $a$ can be seen to be reducible to this special case with not much effort. $\endgroup$ – Emil Jeřábek Nov 28 '12 at 16:59
Seems to me that you could encode SAT in the usual polynomial manner, with variables restricted to being 0 or 1.

$\begingroup$ Do you mean we can take such a Diophantine problem and encode as an SAT instance? This seems right, but the other direction is the more interesting one and it isn't obvious to me: that any SAT formula can be encoded as such a normbounded Diophantine equation. $\endgroup$ – R Hahn Aug 23 '10 at 3:14

$\begingroup$ no i meant it the correct way. Take a SAT formula and encode it as a polynomial using $x$ for a variable, $1x$ for its negation, and so on. $\endgroup$ – Suresh Venkat Aug 23 '10 at 4:45

$\begingroup$ note also that it's easy to encode the bounded norm constraint as well, since the total sum of all variables is at most $n$, in addition to the integer constraint. $\endgroup$ – Suresh Venkat Aug 23 '10 at 4:46

$\begingroup$ right, of course. thank you. If I rephrase the problem in terms of at most 9 unknowns  which is sufficient so that the unbounded decision problem is undecidable  this reduction isn't so straightforward. I am editing the question to reflect this more specific case. $\endgroup$ – R Hahn Aug 23 '10 at 5:16