1
$\begingroup$

In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$ a*x^2+b*y= c $$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete.

The solution (x, y) are positive integers.

Query: What are the conditions on values of constants for which solving the problem is Polynomially feasible? Any link to the references?

$\endgroup$
  • $\begingroup$ Do you have a reference for its NP-completeness? $\endgroup$ – D.W. May 29 '15 at 16:04
  • $\begingroup$ Garey and Johnson. A7.2. [AN8] $\endgroup$ – TheoryQuest1 May 29 '15 at 16:07
  • $\begingroup$ The requirement that $x,y$ be positive was not present in the initial iteration of the question, and it does change the problem. It's important to state the problem correctly: its complexity can be sensitive to these kinds of details. $\endgroup$ – D.W. May 29 '15 at 16:08
  • $\begingroup$ True. I missed that part (was wrong to assume that we are implicitly considering positive cases only). $\endgroup$ – TheoryQuest1 May 29 '15 at 16:17
1
$\begingroup$

You shouldn't expect a complete characterization of all parameters that can be solved in polynomial time, but here are two cases where it can be solved in polynomial time:

If $b$ is prime, you can solve this in polynomial time by letting $x = \sqrt{c/a} \pmod{b}$ and then $y=(c-ax^2)/b$. You can compute modular square roots in polynomial time by standard methods.

If $b$ has known factorization, similar methods can be used (use the Chinese remainder theorem).

Dealing with the requirements $x\ge 0,y \ge 0$ (which were added to the question after I wrote this answer) is more challenging. When $b$ is prime, you can enumerate both modular square roots and see if either of them leads to a valid solution. When $b$ is not prime but has known factorization, in the worst case this might require enumerating exponentially many modular square roots (though you might be able to randomly sample a few square roots and hope that at least one will lead to a positive solution).

$\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.