Algorithm for solving binary quadratic Diophantine equations (BQDE) and its CTC Consider an equation of the form:

$Ax^2+Bxy+Cy^2+Dx+Ey+F=0$

where A-F are integer coefficients (binary quadratic Diophantine equation). I consider here the most general form, so assume all coefficients are non-zero. 

Is there an efficient algorithm which can compute integer solutions for this type of equation?
Yes, such algorithms exist, i.e., if only BDQE has integer solutions, then those solutions can be found computationally, however - in exponential time. There is no polynomial time algorithm to tackle it in the general form (at least on a classical, non-quantum computer).

There's more information in Jeff Lagarias's slides for his talk Complexity of Diophantine Equations.