# Is the solution bounded Diophantine problem NP-complete?

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?

• @R Hahn: As Diophantine Mathematician answered, the problem in the revised (v2) question is NP-complete. – Tsuyoshi Ito Aug 23 '10 at 11:54

## 2 Answers

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

• Thank you. I have edited the problem to make it more precise. – R Hahn Aug 23 '10 at 5:21
• What about the sub-problem for $a=1$? $R(b,c) \Leftrightarrow \exists X \exists Y :X^2 + bY - c = 0$ – user22042 Mar 28 '12 at 15:12
• And the answer to this question is that it is also NP-complete. The problem with general $a$ can be seen to be reducible to this special case with not much effort. – 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.

• 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 norm-bounded Diophantine equation. – R Hahn Aug 23 '10 at 3:14
• no i meant it the correct way. Take a SAT formula and encode it as a polynomial using $x$ for a variable, $1-x$ for its negation, and so on. – Suresh Venkat Aug 23 '10 at 4:45
• 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. – Suresh Venkat Aug 23 '10 at 4:46
• 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. – R Hahn Aug 23 '10 at 5:16