Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
    
,thank you for your answer. –  XL _at_China Apr 29 at 3:06
    
@Bjørn, no --- what I wrote is what it says in Garey and Johnson. –  Gerry Myerson Apr 29 at 5:13
    
Is that a Pell equation or just a simple Diophantine equation? –  Bjørn Kjos-Hanssen Apr 29 at 5:16
    
@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. –  Gerry Myerson Apr 29 at 5:35
    
It jumps from p of $ax+by=c$ to NPC of $ax^2+by=c$ –  XL _at_China Apr 29 at 9:46

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.

share|improve this answer
    
,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. –  XL _at_China Apr 29 at 2:21
4  
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 –  Scott Aaronson Apr 29 at 2:58
    
And,under GRH,the computational complexity is $$e^{O(log N log log N)}$$,so I intend to believe that GRH is true –  XL _at_China Apr 29 at 3:04
    
@ScottAaronson,thank you,and there is a reference on wiki link to Hall's paper –  XL _at_China Apr 29 at 3:12
1  
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. –  Emil Jeřábek Apr 29 at 9:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.