# Diophantine equations with bounds on variables

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?

• No, it’s NP-complete. That it is in NP should be obvious; NP-hardness follows from easy reduction from 3SAT. Sep 23 at 20:36
• @EmilJeřábek, write that as an answer, so we can upvote it?
– D.W.
Sep 24 at 5:49
• I don't think this is a research-level question. It would be more appropriate for cs.stackexchange.com. Sep 24 at 8:27
• @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. Sep 24 at 14:29
• @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; ... Sep 24 at 15:50

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.

• 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. Sep 24 at 15:53
• 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. Sep 24 at 16:01
• @EmilJeřábek Oops, you're right about that last paragraph! Just edited to mention this.
– GMB
Sep 24 at 16:04
• 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?
– GMB
Sep 24 at 16:07
• All right, thank you. Sep 24 at 17:12