Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
@R Hahn: As Diophantine Mathematician answered, the problem in the revised (v2) question is NP-complete. –  Tsuyoshi Ito Aug 23 '10 at 11:54
add comment

2 Answers 2

up vote 16 down vote accepted

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

share|improve this answer
    
Thank you. I have edited the problem to make it more precise. –  R Hahn Aug 23 '10 at 5:21
    
What about the sub-problem for $a=1$? $R(b,c) \Leftrightarrow \exists X \exists Y :X^2 + bY - c = 0$ –  user22042 Mar 28 '12 at 15:12
    
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. –  Emil Jeřábek Nov 28 '12 at 16:59
add comment

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

share|improve this answer
    
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. –  R Hahn Aug 23 '10 at 3:14
    
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. –  Suresh Venkat Aug 23 '10 at 4:45
    
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. –  Suresh Venkat Aug 23 '10 at 4:46
    
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. –  R Hahn Aug 23 '10 at 5:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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