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?