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 NP-complete. $\endgroup$ – Tsuyoshi Ito Aug 23 '10 at 11:54

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 Aug 23 '10 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 Mar 28 '12 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 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 norm-bounded 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, $1-x$ 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.