1
$\begingroup$

What is computational complexity for computing integral solution of Pell equation .It seems to be in P ,and could any one give an algorithm and reference for proof of it's complexity?

And more,could any one give reference for computational complexity for computing integral solution for computable Diophantine equations that have been studied?Thanks.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

Given positive integers $a,b,c$, the problem of deciding whether there are positive integers $x,y$ such that $ax^2+by=c$ is NP-complete. This is entry [AN8] on page 250 of Garey and Johnson, Computers and Intractability, where it is attributed to Manders and Adleman, NP-complete decision problems for binary quadratics, J Comput System Sci 16 (1978) 168-184. There is some discussion in the book, and a further reference to Gurari and Ibarra, An NP-complete number theoretic problem, Proc 10th Ann ACM Symp on Theory of Computing (1978) 205-215.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @Bjørn, no --- what I wrote is what it says in Garey and Johnson. $\endgroup$
    – Gerry Myerson
    Commented Apr 29, 2014 at 5:13
  • $\begingroup$ Is that a Pell equation or just a simple Diophantine equation? $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Apr 29, 2014 at 5:16
  • $\begingroup$ @Bjørn, I wouldn't call it a Pell equation. It's in reference to the second paragraph of the question XL posted, which was about "computable Diophantine equations" generally. $\endgroup$
    – Gerry Myerson
    Commented Apr 29, 2014 at 5:35
  • $\begingroup$ It jumps from p of $ax+by=c$ to NPC of $ax^2+by=c$ $\endgroup$
    – XL _At_Here_There
    Commented Apr 29, 2014 at 9:46
3
$\begingroup$

The problem of finding $x$ and $y$ in a given Pell equation $x^2-ny^2=1$ is not known to be solvable in polynomial time, see Wikipedia.

Improve this answer
$\endgroup$
6
  • $\begingroup$ ,thank you ,It is really strange that computational complexity for so simple a Diophantine equation is still an open problem,And I think it is possibly hopeless to get answer for any other kind of Diophantine equation. $\endgroup$
    – XL _At_Here_There
    Commented Apr 29, 2014 at 2:21
  • 4
    $\begingroup$ On the other hand, solving Pell's equation is known to be in BQP (that is, to admit a polynomial-time quantum algorithm). See here: cse.psu.edu/~hallgren/pell.pdf $\endgroup$
    – Scott Aaronson
    Commented Apr 29, 2014 at 2:58
  • $\begingroup$ And,under GRH,the computational complexity is $$e^{O(log N log log N)}$$,so I intend to believe that GRH is true $\endgroup$
    – XL _At_Here_There
    Commented Apr 29, 2014 at 3:04
  • $\begingroup$ @ScottAaronson,thank you,and there is a reference on wiki link to Hall's paper $\endgroup$
    – XL _At_Here_There
    Commented Apr 29, 2014 at 3:12
  • 2
    $\begingroup$ Pell’s equation is always solvable, so its solvability is most certainly in P. The question is about computing a solution to the equation, which is not a decision problem, but a search problem. So, I don’t even know what’s NP supposed to mean here, but anyway I don’t understand how an exponential lower bound on the number of digits could imply NP-easiness. In fact, if I read NP as TFNP, the fact that the least solution may have superpolynomial length by itself implies the problem is not in TFNP. $\endgroup$
    – Emil Jeřábek
    Commented Apr 29, 2014 at 9:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .