# Calculating Time Complexity of Quadratic Diophantine Equation

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?

• – Raphael Jun 19 '15 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' – TheoryQuest1 Jun 19 '15 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.. – François Jun 19 '15 at 14:30