[Solved]: Computational complexity of finding the roots of a polyomial

Problem Detail: 

I'm currently dealing with a problem for which I could show that an exact algorithm would imply a general algorithm for finding the real (but not complex) roots of an arbitrary univariate polynomial with real coefficients.

Now, what exactly are the implications for my problem?

It is well-known that there is no formula that describes the roots of a polynomial of degree $\geq 5$ and, as far as I know, there is no general algorithm that computes the roots exactly. But are there results stating that the problem is computationally intractable in general? Or is it a common assumption? My question is not aiming at existence results or approximation algorithms but at the computational complexity of the problem and possible implications for my problem.

Note: My algorithm works in the Blum-Shub-Smale model, so the possibly infinite representations of the solutions don't bother me.

Asked By : user1742364

Answered By : cody

It's not too hard to find the real roots of a univariate polynomial, for example by using Sturm's theorem which allows you to easily identify the number of sign changes of a real-valued polynomial between two given bounds.

I believe it's not too hard to show that this technique, coupled with a simple divide-and-conquer technique or Newton's method and an elementary bound on the absolute value of the largest root as a function of the coefficients, gives a polynomial time algorithm for finding the roots of a polynomial, in the time of the degree $n$ and the desired precision $p$ (in digits).

For more information see the wikipedia article or this mathoverflow question.

---

Edit: The question was clarified to ask about exact solutions in the Blum-Shub-Smale model. In this situation, it is already impossible to get square roots, in particular to get exact solutions to the equation $$ X^2 - 2 = 0$$

This result (and a much more general one) is proven in this paper by Calvert, Kramer and Miller.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/46920