<p>No , as far as i know diaphantine problem in general is undecidable thus equivalent to halting problem , if the equations are restricted to be quadratic then it is np-complete , and linear diaphantine equation can be reduced to integer programming problem and For linear Diophantine equation equations, integral solutions exist if and only if, the GCD of coefficients of the two variables divides the constant term perfectly.</p>

CC BY-SA 3.0
2017-12-10T17:42:03.463Z
2017-12-10T17:42:03.463Z
thecomplexitytheorist
<p>In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem.  I believe that deciding if a quadratic diophantine equation has any solution is NP-complete. Does there exist a further restriction on the equations involved that yields a P-complete problem?</p>

CC BY-SA 3.0
2017-12-06T21:19:02.743Z
I think a problem related to gcd was shown P complete.
Turbo
CC BY-SA 3.0
2017-12-07T17:00:44.610Z
Not quite an answer, but it is known that determining if a system of linear equations with integer coefficients has a solution in *rationals* is P-complete.
mhum
CC BY-SA 3.0
2017-12-08T09:57:39.593Z
@mhum Are you sure? Why isn't this problem in the much smaller class DET?
Emil Jeřábek
CC BY-SA 3.0
2017-12-08T15:37:31.960Z
@EmilJeřábek Oops, I mis-stated the result. The solution must be in the *positive* rationals. It's listed as problem A.4.2 in *[A Compendium of Problems Complete for P](https://era.library.ualberta.ca/files/hd76s1312/TR91-11.pdf)*, a 1991 Tech. Report by Greenlaw, et al.
mhum
CC BY-SA 3.0
2017-12-08T17:30:46.920Z
@mhum Oh I see, that makes sense. Thanks for the clarification.
Emil Jeřábek
CC BY-SA 3.0
2017-12-12T17:01:22.053Z
@mhum the "rationals" part of it doesn't change anything, does it? any system of linear inequalities which has a solution, also has one over the rationals.
Sasho Nikolov
CC BY-SA 3.0
2017-12-12T17:23:07.647Z
@SashoNikolov Diophantine equations are understood to ask for solutions in *integers*. This makes a lot of difference here (solvability of linear equations in positive integers is NP-complete).
Emil Jeřábek
CC BY-SA 3.0
2017-12-12T19:24:58.543Z
@EmilJeřábek Of course over the integers this is just integer programming. What I meant is that making linear programming sound like a diophantine equations-type problem by saying you want a rational solution is a bit misleading because insisting on a rational solution adds no constraint to the problem. I.e. if you asked whether the system of linear equations had a solution over the non-negative reals the problem would be exactly the same.
Sasho Nikolov
CC BY-SA 3.0
2017-12-13T09:32:38.427Z
@SashoNikolov It's not a constraint. Without specifying the domain for solutions, the problem is simply *ill-formed*, unless the domain can be inferred from the context. And here the context is such that the implied domain would be the integers, hence one needs to explicitly state it is something different. Yes, here it does not matter whether one picks the rationals, reals, or any other field of characteristic 0. Mhum's choice to call it "rational" is equally valid as your choice to call it "real".
Emil Jeřábek
CC BY-SA 3.0
2017-12-13T16:35:56.043Z
@EmilJeřábek I mostly agree with what you saying. What I am somehow failing to convey is that to me linear programming lacks the number theoretic aspect of the diophantine equations problem.
Sasho Nikolov
CC BY-SA 3.0
2017-12-13T16:38:15.077Z
Does anyone know if solving a system of linear equations over the integers is P-complete?
Sasho Nikolov
<cc.complexity-theory><linear-algebra><polynomials>
Is there a P-complete problem on diophantine equations?
Jacob Edelman
# Is there a P-complete problem on diophantine equations?

(Asked by: username_0 on 2017-12-06)

In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem. I believe that deciding if a quadratic diophantine equation has any solution is NP-complete. Does there exist a further restriction on the equations involved that yields a P-complete problem?

**Tags:** cc.complexity-theory, linear-algebra, polynomials
> **Comments:**
> **username_1**: I think a problem related to gcd was shown P complete.  
> **username_2**: Not quite an answer, but it is known that determining if a system of linear equations with integer coefficients has a solution in *rationals* is P-complete.  
> **username_3**: @mhum Are you sure? Why isn't this problem in the much smaller class DET?  
> **username_2**: @EmilJeřábek Oops, I mis-stated the result. The solution must be in the *positive* rationals. It's listed as problem A.4.2 in *[A Compendium of Problems Complete for P](https://era.library.ualberta.ca/files/hd76s1312/TR91-11.pdf)*, a 1991 Tech. Report by Greenlaw, et al.  
> **username_3**: @mhum Oh I see, that makes sense. Thanks for the clarification.  
> **username_4**: @mhum the "rationals" part of it doesn't change anything, does it? any system of linear inequalities which has a solution, also has one over the rationals.  
> **username_3**: @SashoNikolov Diophantine equations are understood to ask for solutions in *integers*. This makes a lot of difference here (solvability of linear equations in positive integers is NP-complete).  
> **username_4**: @EmilJeřábek Of course over the integers this is just integer programming. What I meant is that making linear programming sound like a diophantine equations-type problem by saying you want a rational solution is a bit misleading because insisting on a rational solution adds no constraint to the problem. I.e. if you asked whether the system of linear equations had a solution over the non-negative reals the problem would be exactly the same.  
> **username_3**: @SashoNikolov It's not a constraint. Without specifying the domain for solutions, the problem is simply *ill-formed*, unless the domain can be inferred from the context. And here the context is such that the implied domain would be the integers, hence one needs to explicitly state it is something different. Yes, here it does not matter whether one picks the rationals, reals, or any other field of characteristic 0. Mhum's choice to call it "rational" is equally valid as your choice to call it "real".  
> **username_4**: @EmilJeřábek I mostly agree with what you saying. What I am somehow failing to convey is that to me linear programming lacks the number theoretic aspect of the diophantine equations problem.  
> **username_4**: Does anyone know if solving a system of linear equations over the integers is P-complete?  

---

## 1 answers

### Answer by username_5 on 2017-12-10. Score: -3

No , as far as i know diaphantine problem in general is undecidable thus equivalent to halting problem , if the equations are restricted to be quadratic then it is np-complete , and linear diaphantine equation can be reduced to integer programming problem and For linear Diophantine equation equations, integral solutions exist if and only if, the GCD of coefficients of the two variables divides the constant term perfectly.


---

