# What is the relation between computational complexity of algebraic number and computational complexity to find the solution to algebraic equation?

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.

## migrated from cstheory.meta.stackexchange.comDec 26 '17 at 20:23

This question came from our discussion, support, and feature requests site for theoretical computer scientists and researchers in related fields.

• 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? – Joshua Grochow Dec 27 '17 at 16:53
• 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), ... – Kaveh May 6 '18 at 23:20