BSS-model Computational complexity of finding the roots of a polyomial
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.