Suppose $\alpha$ is algebraic number, and we have the algorithm with lowest computational complexity to output it, and $f(x)=0$ is algebraic polynomial with $\alpha$ as a root.

If an algorithm which solve the equation and find the root with lowest computational complexity, what is the relation between the computational complexities of the two algorithm? It seems that they are identified and possibly are the same algorithm.

  • 3
    $\begingroup$ We have very few techniques for proving that a given algorithm is optimal, especially in such a deep domain as (what is essentially) number theory. I'd expect that for most algebraic numbers nothing better is currently known, and for all numbers no proof of optimality is known. You might change your question to: "are there any algebraic numbers for which a better algorithm is known?" Related: say I want to compute a given $\alpha$. Does the complexity change if I apply root finding to its minimum polynomial vs some other polynomial with $\alpha$ as a root? $\endgroup$ – Joshua Grochow Dec 27 '17 at 16:53
  • $\begingroup$ I think the question is under defined: how are real numbers represented, f is not uniquely determined from alpha, which uniform root finding algorithm (you have to fix it or and there isn't a necessarily a generally optimal one), ... $\endgroup$ – Kaveh May 6 '18 at 23:20

Your Answer

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

Browse other questions tagged or ask your own question.