0
$\begingroup$

Solving Diophantine equations is famously known to be undecidable. What about Diophantine equations to be solved over a finite domain? In particular, if I put an upper bound $k$ over the value of the variables, clearly the problem becomes decidable.

But what is the complexity? My guess is PSPACE-complete, am I correct?

$\endgroup$
7
  • 1
    $\begingroup$ No, it’s NP-complete. That it is in NP should be obvious; NP-hardness follows from easy reduction from 3SAT. $\endgroup$ Sep 23 at 20:36
  • $\begingroup$ @EmilJeřábek, write that as an answer, so we can upvote it? $\endgroup$
    – D.W.
    Sep 24 at 5:49
  • $\begingroup$ I don't think this is a research-level question. It would be more appropriate for cs.stackexchange.com. $\endgroup$ Sep 24 at 8:27
  • 1
    $\begingroup$ @EmilJeřábek - if $k$ is given in binary, it's not trivial that the problem is in NP (I'm not sure if it's the case). I think this case is research-level. $\endgroup$
    – Shaull
    Sep 24 at 14:29
  • 1
    $\begingroup$ @Shaull It is trivial. You guess the values of the variables. They have length in binary bounded by the length of $k$ in binary. Then you evaluate the polynomials to verify the results are $0$. This works in polynomial time, as the intermediate results again have length polynomial in the length of $k$. The only subtle point here is the representation if the polynomial. I’m assuming it is given as a sum of monomials; the argument above applies mnore generally if they are given by arithmetic formulas. If they are given by arithmetic circuits, the intermediate results might be exponential; ... $\endgroup$ Sep 24 at 15:50
3
$\begingroup$

Edit from discussion in comments below: There are two related questions here. One is "What languages can be described by Diophantine polynomials with polynomially-bounded inputs?" This is the complexity class $D$, described in this answer. The other is "What is the complexity of the decision problem of whether a Diophantine polynomial has a solution with bounded variables?" This is NP-Complete, as discussed by Emil.


The class you are describing is contained in NP, but it's a significant open question in complexity theory to determine whether or not it's equal to NP. The state-of-the-art Diophantine encodings don't work to encode a nondeterministic 3SAT algorithm as a Diophantine polynomial, for a subtle reason: some basic computational primitives, essentially for-loops, currently requires a double-exponential blowup. That is, to encode a program with an iterator variable $i = 1, \dots, n$ as a Diophantine polynomial that accepts the same set of integers, one will have to allow one of the existentially-quantified input variables to range up to about $2^{2^n}$. So there are some languages in P that are not known to be expressible as Diophantine polynomials with exponentially-bounded inputs.

The paper "Diophantine Complexity" by Adelman and Manders (FOCS '76) was the first to set up this theory. They define the complexity class $D$ as the sets of natural numbers $S_p$ that can be expressed in the form $$S_p = \{ x \ \mid \ \exists y_1, \dots, y_n \le 2^\text{poly(n)} \text{ such that } p(x, y_1, \dots, y_n) = 0 \}$$ for some Diophantine polynomial $p$. Clearly $D \subseteq NP$, since we can guess values for the $y_i$ variables. Their central question in this paper is whether $D=NP$. They provide several "$D$-Complete" problems, meaning problems in $D$ iff $D=NP$. For example, one of the $D$-Complete problems is the regular language $R=(10+00)^*$.

((The best known upper bound on $D$ is by Knop, who proves that $D$ is contained in the second level of the polynomial hierarchy. This paper also sets up a hierarchy above $D$ similar to the polynomial hierarchy.))

Oops! This last paragraph is false, there must be a typo somewhere in that paper abstract. Thanks Emil.

$\endgroup$
10
  • $\begingroup$ The question didn’t ask what is D; it asked about the complexity of the problem. Whether or not D equals NP is irrelevant; what matters is that the problem is NP-complete, i.e., the closure of D under polynomial-time reductions is NP. This is indeed trivial to prove by reduction from 3SAT. $\endgroup$ Sep 24 at 15:53
  • 1
    $\begingroup$ Also, the two claims that “clearly, D is a subset of NP” and that the best upper bound on D is the second level of PH contradict each other. I cannot access Knop’s article, but it seems that there is a typo in the abstract, and what is really meant here is that NP is contained in the second level of the D hierarchy. $\endgroup$ Sep 24 at 16:01
  • $\begingroup$ @EmilJeřábek Oops, you're right about that last paragraph! Just edited to mention this. $\endgroup$
    – GMB
    Sep 24 at 16:04
  • $\begingroup$ I agree that the closure of D under polytime reductions is NP, and that the 3SAT reduction works if we allow these polytime reductions. But that's not how I interpreted OP's original question. The question is based on the original MRDP theorem, which does not say anything about closures: it says that the languages defined as above but without bounds on the $y_i$ variables is exactly RE. So I didn't think OP was asking about closures. Perhaps they can clarify? $\endgroup$
    – GMB
    Sep 24 at 16:07
  • 1
    $\begingroup$ All right, thank you. $\endgroup$ Sep 24 at 17:12

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.