<p>This paper, <a href="http://www.sciencedirect.com/science/article/pii/0196677487900137" rel="nofollow">Computational complexities of Diophantine equations with parameters</a> by Tung, proves co-NP-completeness of a variant with parameters over natural numbers.</p>

CC BY-SA 3.0
2013-05-02T16:21:49.683Z
2013-05-02T16:21:49.683Z
Mohammad Al-Turkistany
<p>Note that it depends a lot on what set are you solving over.
For example, the NP-complete SUBSET-SUM problem can be considered as a LINEAR DIOPHANTNE EQUATION, when you restrict your solution over positive integers.
If you allow also negative solutions then it is solvable in polynomial time.
For an excellent survey, see:</p>

<p>[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.3864][1]</p>

CC BY-SA 3.0
2013-05-02T16:01:00.670Z
2013-05-02T16:01:00.670Z
Lior Eldar
<p>LINEAR DIOPHANTINE EQUATIONS 
(given natural numbers $a, b, c$, are there natural numbers $x$ and $y$ such that $ax + by + c = 0$?) are solvable in polynomial time.</p>

<p>QUADRATIC DIOPHANTINE EQUATIONS ($ax^2 + by + c = 0$) are NP-complete (<a href="http://dl.acm.org/citation.cfm?id=803627">NP-complete decision problems for quadratic polynomials</a>).</p>

<p>General DIOPHANTINE EQUATIONS are undecidable (Davis-Putnam-Robinson-Matiyasevich theorem).</p>

<blockquote>
Are there other classes of Diophantine equations (with restrictions on their arguments/variables) that capture other complexity classes (in particular PSPACE) ?
</blockquote>

<reference-request>
Diophantine equations and complexity classes
Marzio De Biasi
# Diophantine equations and complexity classes

(Asked by: username_0 on 2013-05-02)

LINEAR DIOPHANTINE EQUATIONS
(given natural numbers $a, b, c$, are there natural numbers $x$ and $y$ such that $ax + by + c = 0$?) are solvable in polynomial time.

QUADRATIC DIOPHANTINE EQUATIONS ($ax^2 + by + c = 0$) are NP-complete ([NP-complete decision problems for quadratic polynomials](http://dl.acm.org/citation.cfm?id=803627)).

General DIOPHANTINE EQUATIONS are undecidable (Davis-Putnam-Robinson-Matiyasevich theorem).

> Are there other classes of Diophantine equations (with restrictions on their arguments/variables) that capture other complexity classes (in particular PSPACE) ?

**Tags:** reference-request

---

## 2 answers

### Answer by username_1 on 2013-05-02. Score: 4

This paper, [Computational complexities of Diophantine equations with parameters](http://www.sciencedirect.com/science/article/pii/0196677487900137) by Tung, proves co-NP-completeness of a variant with parameters over natural numbers.


---

### Answer by username_2 on 2013-05-02. Score: 3

Note that it depends a lot on what set are you solving over.
For example, the NP-complete SUBSET-SUM problem can be considered as a LINEAR DIOPHANTNE EQUATION, when you restrict your solution over positive integers.
If you allow also negative solutions then it is solvable in polynomial time.
For an excellent survey, see:

[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.3864][1]


---

