12
$\begingroup$

'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?

$\endgroup$
  • 2
    $\begingroup$ Why is the first problem NP-complete? A reference would be appreciated. :) $\endgroup$ – Michael Wehar Aug 13 '15 at 15:36
  • 2
    $\begingroup$ @MichaelWehar, Quadratic Diophantine is NP-complete. I think it is even in Gary and Johnson. $\endgroup$ – Kaveh Aug 13 '15 at 16:33
  • 2
    $\begingroup$ It is AN8 in Garey and Johnson, page 250: Manders and Adleman, "NP-complete decision problems for binary quadratics",1978. $\endgroup$ – Kaveh Aug 13 '15 at 16:40
  • 4
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Aug 14 '15 at 9:56
  • 5
    $\begingroup$ 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 . $\endgroup$ – Emil Jeřábek Aug 14 '15 at 10:05
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ I do not this is a good answer (it states the obvious). $\endgroup$ – user34945 Aug 13 '15 at 18:30
  • 2
    $\begingroup$ This seems to answer the question that was asked. If you were intending further conditions, you need to include them in the question. $\endgroup$ – András Salamon Aug 13 '15 at 21:30
  • 4
    $\begingroup$ @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. $\endgroup$ – Kaveh Aug 13 '15 at 22:49
  • 1
    $\begingroup$ @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? $\endgroup$ – András Salamon Aug 13 '15 at 23:57
  • 4
    $\begingroup$ @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. $\endgroup$ – Kaveh Aug 14 '15 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy