<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-12-27T16:53:33.947Z
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
CC BY-SA 4.0
2018-05-06T23:20:24.903Z
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
<algebraic-complexity>
What is the relation between computational complexity of algebraic number and computational complexity to find the solution to algebraic equation?
XL _At_Here_There
# What is the relation between computational complexity of algebraic number and computational complexity to find the solution to algebraic equation?

(Asked by: username_0 on 2017-12-24)

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.

**Tags:** algebraic-complexity

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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), ...  

---

## 0 answers

