  Binary quadratic Diophantine equations are of interest from the viewpoint of
computational complexity theory. They contain as special cases many examples of
natural problems apparantly occupying intermediate stages in the P-NP
hierarchy, i.e. problems neither known to be polynomial time or NP-complete.
Let L(F) denote the length of the binary encoding of the coefficients of a
binary quadratic diophantine equation F(x_1, x_2)=0. This paper shows there is
a certificate of length polynomial in L(F) that such an equation has an integer
solution (resp. positive integer solution) when one exists. This is interesting
because it is known there exist such equations whose minimal nonnegative
integer solution is so large that it requires space exponential in L(F) to
write it down in binary representation. The certificates are based on the ideas
of D. Shank's "infrastructure".
