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 ItoCommented 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
answered Aug 23, 2010 at 4:05
-
$\begingroup$ Thank you. I have edited the problem to make it more precise. $\endgroup$– R HahnCommented 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$– user22042Commented 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$ Commented 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.
answered Aug 23, 2010 at 2:21
-
$\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 HahnCommented 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$ Commented 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$ Commented 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 HahnCommented Aug 23, 2010 at 5:16