# Calculating Time Complexity of 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?

• Jun 19, 2015 at 12:02
• 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' Jun 19, 2015 at 12:49
• 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.. Jun 19, 2015 at 14:30