The particular quadratic Diophantine equation:

$$ R(a,b,c) \Leftrightarrow \exists X \exists Y :aX^2 + bY - c = 0 $$

is NP-complete. (a, b, and c are given in their binary representations. a, b, c, X, and Y are positive integers).

Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Quadratic Polynomials. STOC 1976: 23-29

Since, I do not have the access to the stated paper, can someone help with how the time complexity (clearly exponential) varies/depends on the size of a, b, and c?

  • $\begingroup$ Related question. $\endgroup$
    – Raphael
    Jun 19, 2015 at 12:02
  • $\begingroup$ Thanks.. that Q is different.. the Q I have is different here: Let a, b, c be some constants in a Quadratic Diophantine Equation. How will the computational complexity of the problem be affected w.r.t. the changing (lets assume doubling) the size (Number of Bits) in these cases: 1. just 'a' 2. just 'b' 3. just 'c' $\endgroup$ Jun 19, 2015 at 12:49
  • 1
    $\begingroup$ I read diagonally the paper and I didn't see any formula for the complexity, they just said things like "Moreover, we can obtain all quantities needed deterministically within polynomial time in the length of the input" etc.. $\endgroup$
    – François
    Jun 19, 2015 at 14:30


Your Answer

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