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$ $\endgroup$
1 
- 1$\begingroup$ @R Hahn: As Diophantine Mathematician answered, the problem in the revised (v2) question is NP-complete. $\endgroup$Tsuyoshi Ito– Tsuyoshi Ito2010-08-23 11:54:11 +00:00Commented Aug 23, 2010 at 11:54
Add a comment |
2 Answers
$\begingroup$ $\endgroup$
3 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
- $\begingroup$ Thank you. I have edited the problem to make it more precise. $\endgroup$R Hahn– R Hahn2010-08-23 05:21:50 +00:00Commented Aug 23, 2010 at 5:21
- $\begingroup$ What about the sub-problem for $a=1$? $R(b,c) \Leftrightarrow \exists X \exists Y :X^2 + bY - c = 0$ $\endgroup$user22042– user220422012-03-28 15:12:09 +00:00Commented Mar 28, 2012 at 15:12
- $\begingroup$ 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. $\endgroup$Emil Jeřábek– Emil Jeřábek2012-11-28 16:59:57 +00:00Commented Nov 28, 2012 at 16:59
$\begingroup$ $\endgroup$
4 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 norm-bounded Diophantine equation. $\endgroup$R Hahn– R Hahn2010-08-23 03:14:47 +00:00Commented Aug 23, 2010 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, $1-x$ for its negation, and so on. $\endgroup$Suresh Venkat– Suresh Venkat2010-08-23 04:45:35 +00:00Commented Aug 23, 2010 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– Suresh Venkat2010-08-23 04:46:22 +00:00Commented Aug 23, 2010 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– R Hahn2010-08-23 05:16:05 +00:00Commented Aug 23, 2010 at 5:16