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.

$\endgroup$

2 Answers 2

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.

$\endgroup$
4
  • $\begingroup$ @Bjørn, no --- what I wrote is what it says in Garey and Johnson. $\endgroup$ Apr 29, 2014 at 5:13
  • $\begingroup$ Is that a Pell equation or just a simple Diophantine equation? $\endgroup$ 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$ Apr 29, 2014 at 5:35
  • $\begingroup$ It jumps from p of $ax+by=c$ to NPC of $ax^2+by=c$ $\endgroup$ 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.

$\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$ 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$ 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$ Apr 29, 2014 at 3:04
  • $\begingroup$ @ScottAaronson,thank you,and there is a reference on wiki link to Hall's paper $\endgroup$ 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$ Apr 29, 2014 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.