11
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I think a problem related to gcd was shown P complete. $\endgroup$ – T.... Dec 6 '17 at 21:19
  • 3
    $\begingroup$ @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. $\endgroup$ – mhum Dec 8 '17 at 15:37
  • 2
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Dec 12 '17 at 19:24
  • 1
    $\begingroup$ @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". $\endgroup$ – Emil Jeřábek Dec 13 '17 at 9:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Sasho Nikolov Dec 13 '17 at 16:35
-3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.