most recent 30 from http://mathoverflow.net 2013-05-21T23:22:25Z http://mathoverflow.net/feeds/question/36420 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36420/is-the-solution-bounded-diophantine-problem-np-complete R Hahn 2010-08-23T01:58:33Z 2012-03-28T15:12:09Z

<p>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?</p>

http://mathoverflow.net/questions/36420/is-the-solution-bounded-diophantine-problem-np-complete/36422#36422 Suresh Venkat 2010-08-23T02:21:33Z 2010-08-23T02:21:33Z

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

http://mathoverflow.net/questions/36420/is-the-solution-bounded-diophantine-problem-np-complete/36424#36424 Diophantine Mathematician 2010-08-23T04:05:06Z 2010-08-23T04:05:06Z

<p>A particular quadratic Diophantine equation is NP-complete.</p> <p>$R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY - c = 0$</p> <p>is NP-complete. ($a$, $b$, and $c$ are given in their binary representations. $a$, $b$, $c$, $X$, and $Y$ are positive integers).</p> <p>Note that there are trivial bounds on the sizes of $X$ and $Y$ in terms of $a$, $b$, and $c$.</p> <p>Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Quadratic Polynomials. STOC 1976: 23-29</p>

http://mathoverflow.net/questions/36420/is-the-solution-bounded-diophantine-problem-np-complete/92463#92463 unknown (google) 2012-03-28T15:12:09Z 2012-03-28T15:12:09Z

<p>What about the sub-problem of the answered one for $a=1$?</p> <p>$R(b,c) \Leftrightarrow \exists X \exists Y :X^2 + bY - c = 0$</p>