# BSS-model Computational complexity of finding the roots of a polyomial

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.

• It's definitely undecidable w.r.t. integer solutions, but I don't know about the continuous case (other than that it's certainly not Turing-computable, but you have already transcended that model). – Raphael Sep 7 '15 at 15:13
• @Raphael, a small correction: Deciding whether a multivariate integer polynomial has an integer solution is undecidable. For univariate polynomials, it's decidable. In fact I think it can be done in polynomial time. See en.wikipedia.org/wiki/Factorization_of_polynomials. – D.W. Sep 7 '15 at 17:13
• Please edit the question to state state what kind of polynomial you can find roots for. Is it a univariate polynomial? Multivariate? What kinds of roots are we talking about? Integer roots to a polynomial with integer coefficients? Rational roots and rational coefficients? Real numbers? Complex numbers? A finite field? Something else? The complexity of finding roots of a polynomial depends greatly upon these specific details. – D.W. Sep 7 '15 at 17:15
• What exactly do you mean by "determine (...) exactly"? There are uncountably many reals, and any finitary language can only describe countably many. Do you mean that you can give arbitrarily close approximations? – Klaus Draeger Sep 8 '15 at 11:51
• OK, so you're asking about the complexity of finding roots for univariate real-valued polynomials in the BSS model (e.g., is it NP-hard, for the BSS analog of NP-hard?). Cool. The original BSS paper proved that testing whether a multivariate polynomial $f:\mathbb{R}^n \to \mathbb{R}$ of degree 4 has a root is NP-complete (in the BSS model), but I don't know what happens for univariate polynomials. – D.W. Sep 9 '15 at 1:53

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).

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$$