<p><strong>Edit</strong> from discussion in comments below: There are two related questions here.  One is &quot;What languages can be described by Diophantine polynomials with polynomially-bounded inputs?&quot;  This is the complexity class <span class="math-container">$D$</span>, described in this answer.  The other is &quot;What is the complexity of the decision problem of whether a Diophantine polynomial has a solution with bounded variables?&quot;  This is NP-Complete, as discussed by Emil.</p>
<hr />
<p>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 <em>don't</em> 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 <em>double-exponential</em> blowup.  That is, to encode a program with an iterator variable <span class="math-container">$i = 1, \dots, n$</span> 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 <span class="math-container">$2^{2^n}$</span>.  So there are some languages in P that are not known to be expressible as Diophantine polynomials with exponentially-bounded inputs.</p>
<p>The paper <a href="https://ieeexplore.ieee.org/document/4567891" rel="nofollow noreferrer">&quot;Diophantine Complexity&quot;</a> by Adelman and Manders (FOCS '76) was the first to set up this theory.  They define the complexity class <span class="math-container">$D$</span> as the sets of natural numbers <span class="math-container">$S_p$</span> that can be expressed in the form
<span class="math-container">$$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 \}$$</span>
for some Diophantine polynomial <span class="math-container">$p$</span>.
Clearly <span class="math-container">$D \subseteq NP$</span>, since we can guess values for the <span class="math-container">$y_i$</span> variables.
Their central question in this paper is whether <span class="math-container">$D=NP$</span>.  They provide several &quot;<span class="math-container">$D$</span>-Complete&quot; problems, meaning problems in <span class="math-container">$D$</span> iff <span class="math-container">$D=NP$</span>.  For example, one of the <span class="math-container">$D$</span>-Complete problems is the regular language <span class="math-container">$R=(10+00)^*$</span>.</p>
<p><em>((The <a href="https://link.springer.com/article/10.1007/s10958-012-1106-7" rel="nofollow noreferrer">best known upper bound</a> on <span class="math-container">$D$</span> is by Knop, who proves that <span class="math-container">$D$</span> is contained in the second level of the polynomial hierarchy.  This paper also sets up a hierarchy above <span class="math-container">$D$</span> similar to the polynomial hierarchy.))</em></p>
<p>Oops!  This last paragraph is false, there must be a typo somewhere in that paper abstract.  Thanks Emil.</p>

CC BY-SA 4.0
2021-09-24T15:53:13.817Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T16:01:09.410Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T16:04:59.383Z
@EmilJeřábek Oops, you're right about that last paragraph!  Just edited to mention this.
GMB
CC BY-SA 4.0
2021-09-24T16:07:16.003Z
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
CC BY-SA 4.0
2021-09-24T16:14:51.263Z
The question simply asks about the complexity of a single decision problem: given a Diophantine equation and a bound, does it have a solution obeying the bound. This does not involve any class of problems. The appropriate answer to such a question is *the problem is XXX-complete*, for suitable XXX. The OP even suggests it themselves (he asks if it is PSPACE-complete). So the correct answer to the question is “the problem is NP-complete”.
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T16:27:29.460Z
Sure, I can understand that reading of OP's question.  It's probably more natural than mine and more likely what OP meant, in hindsight.  I think we agree on the math here: the problem is definitely NP-complete under polytime reductions, but not known to be NP-complete under diophantine reductions in the sense of the linked paper, and it is not known whether "the bounded version of the MRDP theorem" captures NP.
GMB
CC BY-SA 4.0
2021-09-24T16:56:22.057Z
So can you write that clearly into the answer? It is extremely misleading as it suggests that the problem might be easier than NP, when it is actually NP-complete.
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T17:05:43.327Z
Sure, I added a pointer.
GMB
CC BY-SA 4.0
2021-09-24T17:12:48.447Z
All right, thank you.
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T17:13:34.750Z
Thanks to all for the discussion!
Nicola Gigante
CC BY-SA 4.0
2021-09-24T14:34:43.790Z
2021-09-24T17:11:16.823Z
2021-09-24T17:11:16.823Z
GMB
<p>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 <span class="math-container">$k$</span> over the value of the variables, clearly the problem becomes decidable.</p>
<p>But what is the complexity? My guess is PSPACE-complete, am I correct?</p>

CC BY-SA 4.0
2021-09-23T20:36:10.080Z
No, it’s NP-complete. That it is in NP should be obvious; NP-hardness follows from easy reduction from 3SAT.
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T05:49:17.807Z
@EmilJeřábek, write that as an answer, so we can upvote it?
D.W.
CC BY-SA 4.0
2021-09-24T08:27:01.503Z
I don't think this is a research-level question. It would be more appropriate for https://cs.stackexchange.com.
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T14:29:10.020Z
@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.
Shaull
CC BY-SA 4.0
2021-09-24T15:50:11.517Z
@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; ...
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T15:50:49.700Z
... in that case, the complexity of checking that the result is $0$ raises to coRP, and the whole problem to MA.
Emil Jeřábek
CC BY-SA 4.0
2021-09-24T19:47:38.540Z
@EmilJeřábek - right, right. I was being stupid. :)
Shaull
<cc.complexity-theory><reference-request>
Diophantine equations with bounds on variables
Nicola Gigante
# Diophantine equations with bounds on variables

(Asked by: username_0 on 2021-09-23)

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?

**Tags:** cc.complexity-theory, reference-request
> **Comments:**
> **username_1**: No, it’s NP-complete. That it is in NP should be obvious; NP-hardness follows from easy reduction from 3SAT.  
> **username_2**: @EmilJeřábek, write that as an answer, so we can upvote it?  
> **username_1**: I don't think this is a research-level question. It would be more appropriate for https://cs.stackexchange.com.  
> **username_3**: @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.  
> **username_1**: @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; ...  
> **username_1**: ... in that case, the complexity of checking that the result is $0$ raises to coRP, and the whole problem to MA.  
> **username_3**: @EmilJeřábek - right, right. I was being stupid. :)  

---

## 1 answers

### Answer by username_4 on 2021-09-24. Score: 3

**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"](https://ieeexplore.ieee.org/document/4567891) 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](https://link.springer.com/article/10.1007/s10958-012-1106-7) 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.

> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_4**: @EmilJeřábek Oops, you're right about that last paragraph!  Just edited to mention this.  
> **username_4**: 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?  
> **username_1**: The question simply asks about the complexity of a single decision problem: given a Diophantine equation and a bound, does it have a solution obeying the bound. This does not involve any class of problems. The appropriate answer to such a question is *the problem is XXX-complete*, for suitable XXX. The OP even suggests it themselves (he asks if it is PSPACE-complete). So the correct answer to the question is “the problem is NP-complete”.  
> **username_4**: Sure, I can understand that reading of OP's question.  It's probably more natural than mine and more likely what OP meant, in hindsight.  I think we agree on the math here: the problem is definitely NP-complete under polytime reductions, but not known to be NP-complete under diophantine reductions in the sense of the linked paper, and it is not known whether "the bounded version of the MRDP theorem" captures NP.  
> **username_1**: So can you write that clearly into the answer? It is extremely misleading as it suggests that the problem might be easier than NP, when it is actually NP-complete.  
> **username_4**: Sure, I added a pointer.  
> **username_1**: All right, thank you.  
> **username_0**: Thanks to all for the discussion!  

---

