# 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. :) Aug 13, 2015 at 15:36
• @MichaelWehar, Quadratic Diophantine is NP-complete. I think it is even in Gary and Johnson. Aug 13, 2015 at 16:33
• It is AN8 in Garey and Johnson, page 250: Manders and Adleman, "NP-complete decision problems for binary quadratics",1978. Aug 13, 2015 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$. Aug 14, 2015 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 . Aug 14, 2015 at 10:05

Added later: As noted in the comments, the NP upper bound is trivial if a, b, and c are positive, as was asked.

Theorem 1.2 in this paper shows that deciding if a given diophantine equation in two variables has a solution is in NP.

• I do not this is a good answer (it states the obvious).
– user34945
Aug 13, 2015 at 18:30
• This seems to answer the question that was asked. If you were intending further conditions, you need to include them in the question. Aug 13, 2015 at 21:30
• @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. Aug 13, 2015 at 22:49
• @Kaveh: yes, but that is not what was asked. Further, I presume a,b,c are given in binary, so x and y are only exponentially bounded in n? Aug 13, 2015 at 23:57
• @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. Aug 14, 2015 at 0:23