# Is there a P-complete problem on diophantine equations?

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?

• I think a problem related to gcd was shown P complete. – Turbo Dec 6 '17 at 21:19
• @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, a 1991 Tech. Report by Greenlaw, et al. – mhum Dec 8 '17 at 15:37
• @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 Dec 12 '17 at 19:24
• @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 Dec 13 '17 at 9:32
• @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 Dec 13 '17 at 16:35