Timeline for Number theory and NP-complete
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 11, 2011 at 2:57 | vote | accept | user16007 | ||
| Aug 11, 2011 at 1:31 | comment | added | boumol | This example is Theorem 1 in the paper "NP-complete decision problems for quadratic polynomials". There you can find the proof of the NP-hard part, but the fact that it belongs to NP is easily proved because there is a solution for $x,y$ iff there is a solution with $x,y\leq c$ (this bound is enough for showing membership in the class NP). The problem that it is known to be undecidable is the one where you allow multiple variables (not just the two $x,y$) and integer coefficients [in the same paper it is noted that it is known that 9 variable are enough for the undecidability]. | |
| Aug 11, 2011 at 1:09 | comment | added | user16007 | Do you happen to know the proof? I had the opinion Diophantine equations usually have only undecidability results. | |
| Aug 11, 2011 at 1:08 | comment | added | user16007 | Good explicit example. Thankyou. | |
| Aug 10, 2011 at 22:45 | history | answered | boumol | CC BY-SA 3.0 |