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$
4
  • $\begingroup$ Do you have a reference for its NP-completeness? $\endgroup$
    – D.W.
    May 29, 2015 at 16:04
  • $\begingroup$ Garey and Johnson. A7.2. [AN8] $\endgroup$ May 29, 2015 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, 2015 at 16:08
  • $\begingroup$ True. I missed that part (was wrong to assume that we are implicitly considering positive cases only). $\endgroup$ May 29, 2015 at 16:17

1 Answer 1

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$
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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