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?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 


Seems to me that you could encode SAT in the usual polynomial manner, with variables restricted to being 0 or 1. 

