5
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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). $\endgroup$
    – Raphael
    Commented Sep 7, 2015 at 15:13
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Commented Sep 7, 2015 at 17:13
  • 2
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Sep 7, 2015 at 17:15
  • 1
    $\begingroup$ 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? $\endgroup$
    – Klaus Draeger
    Commented Sep 8, 2015 at 11:51
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Sep 9, 2015 at 1:53

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Very cool answer! However, it's also worth pointing out that this doesn't quite seem to resolve the question posed here. The question posed here is: what is the complexity of calculating the roots exactly, in the Blum-Shub-Smale model? Your answer says: we can get an infinite sequence of arbitrarily good approximations to roots (in both the ordinary model and the BSS model). However this seems to leave open the question of finding a root exactly, in the BSS model (not just an infinite sequence of approximations to the root that get arbitrarily close to the root). $\endgroup$
    – D.W. ♦
    Commented Sep 9, 2015 at 4:58
  • $\begingroup$ The roots can't be computed exactly in the BSS model (you can only do rational steps at each point). $\endgroup$
    – cody
    Commented Sep 9, 2015 at 13:52
  • $\begingroup$ Thank you, I think this solves my problem. So, the answer for my problem would be that it is computationally intractable since an algorithm would in particular allow to get the square root of a number exactly, which, however, is computationally intractable in the BSS. Right? $\endgroup$
    – user1742364
    Commented Sep 10, 2015 at 8:46
  • 1
    $\begingroup$ Intractable usually means that it takes an unmanageable of computational resources. Here it is simply non-computable (but can be approximated easily to arbitrarily high precision). $\endgroup$
    – cody
    Commented Sep 10, 2015 at 13:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.