# Which complexity class does this number theory problem belong to?

'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by=c$' is $\mathsf{NP}$-complete.

Which complexity class does 'Given $a,b,c\in\Bbb N$, is there $x,y\in\Bbb N$, $ax^2+by^2=c$' belong to?

• Why is the first problem NP-complete? A reference would be appreciated. :) – Michael Wehar Aug 13 '15 at 15:36
• @MichaelWehar, Quadratic Diophantine is NP-complete. I think it is even in Gary and Johnson. – Kaveh Aug 13 '15 at 16:33
• It is AN8 in Garey and Johnson, page 250: Manders and Adleman, "NP-complete decision problems for binary quadratics",1978. – Kaveh Aug 13 '15 at 16:40
• The existence of rational solutions is polynomially reducible to factoring, hence in $\mathrm{NP}\cap\mathrm{coNP}$: using the Hasse principle, it amounts to checking that the Hilbert symbol $(a/c,b/c)_p=1$ for all primes $p\mid2abc$. – Emil Jeřábek Aug 14 '15 at 9:56
• Note that (for either integer or rational solvability) you are unlikely to get anything better than factoring: already the special case $a=b=1$ (i.e., whether $c$ is a sum of two squares) asks whether all primes $p\equiv3\pmod4$ occur in $c$ with even multiplicity, and to the best of my knowledge, it’s not known how to test this more efficiently than factoring $c$; cf. mathoverflow.net/q/57981 . – Emil Jeřábek Aug 14 '15 at 10:05

• @AndrásSalamon, it doesn't, the NP upper bound seems trivial when $a$ and $b$ are both nonnegative (so $x$ and $y$ are polynomially bounded by in $a$, $b$, and $c$). The real question is if it hard for NP. – Kaveh Aug 13 '15 at 22:49
• @AndrásSalamon, Their size are polynomially bounded in $n$. As I said, being in NP is trivial for the problem. The paper is talking about a more general case which the question is not about. – Kaveh Aug 14 '15 at 0:23