16
$\begingroup$
  • Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a polynomial there is no deterministic algorithm to find the roots?

  • Now consider a decision question of the form, "Given a real rooted polynomial $p$ and a number k is the third and the fourth highest root of $p$ at least at a gap of k?"

A proof certificate for this decision question will just be the set of roots of this polynomial and that is short certificate and hence it looks like $NP$ BUT isn't Galois theorem saying that there does not exist any deterministic algorithm to find a certificate for this decision question? (and this property if true rules out any algorithm to decide the answer to this question)

So in what complexity class does this decision question lie in?


All NP-complete questions I have seen always have a trivial exponential time algorithm available to solve them. I don't know if this is expected to be a property which should always be true for all NP-complete questions. For this decision question this doesn't seem to be true.

$\endgroup$
  • 2
    $\begingroup$ The roots are a certificate but it's not obvious to me that they're a short certificate (i.e., that there's a constant $k$ such that, for every polynomial, you can write out its roots in $O(n^k)$ bits, where $n$ is the number of bits required to write down the polynomial). But if there is an NP algorithm, there is a trivial exponential-time algorithm: just enumerate all potential certificates and see if any of them works. $\endgroup$ – David Richerby Apr 17 '15 at 23:57
  • $\begingroup$ A few comments: (1) The roots of $\sum_{i=0}^n a_i x_i$ have absolute values at most $\max(1,\sum_{i=0}^{n-1} |a_i|/|a_n|)$. (2) Sturm sequences can be used to isolate the roots of a polynomial. (3) We can check whether there are two roots at distance exactly $k$, and if so which, by computing the GCD of $p(x)$ and $p(x+k)$. $\endgroup$ – Yuval Filmus Apr 18 '15 at 1:34
  • $\begingroup$ @YuvalFilmus Can any of your above ideas be used to decide the above decision question? Its not obvious if these can be used to decide this question - in polynomial time? $\endgroup$ – user6818 Apr 18 '15 at 3:21
  • 1
    $\begingroup$ "Galois's theorem effectively says that one cannot express the roots of a polynomial of degree >= 5 using rational functions of coefficients and radicals - can't this be read to be saying that given a polynomial there is no deterministic algorithm to find the roots?" No, since polynomial time algorithms are more powerful than rational functions. For example, they can split cases, iterate, create arrays and loop over them etc. $\endgroup$ – sdcvvc Apr 18 '15 at 22:25
  • 2
    $\begingroup$ @user6818 The theorem concerns a specific computation model - rational functions of radicals. If you change the model, it no longer applies. For example, according to MathWorld mathworld.wolfram.com/QuinticEquation.html it's possible to solve the 5th degree equation using Jacobi theta functions. If you are fine with an algorithm that returns the root within 0.01 (or any given $\epsilon > 0$), the Galois theorem will no longer disqualify the method, since any number can be approximated by a rational. $\endgroup$ – sdcvvc Apr 18 '15 at 22:59
5
$\begingroup$

Interesting connection, however Galois theory states that no (consistent) method exists for finding roots of quintic using radicals, instead of saying that the problem has a solution (eg a longest path) which may require super-polynomial time. So i would say it is more related to undecidability rather than complexity.

Specificaly, in Galois theory one progressively builds group extensions of the roots of the equation, in a step-by-step way (adding one root at a time). And all these groups should be solvable, in a sense there should be no ambiguity in the process of constructing these extensions in another order. There is a related question on MO on the complexity of constructing the Galois group of an equation.

Another reference here "COMPUTATIONAL GALOIS THEORY: INVARIANTS AND COMPUTATIONS OVER $\mathbb{Q}$", CLAUS FIEKER JURGEN KLUNERS

Furthermore one can systematicaly represent roots of a polynomial euqation using radicals (when the equation is solvable using radicals) based on the construction of the Galois group(s) of the equation. Ref: "Radical Representation of Polynomial Roots", Hirokazu Anai Kazuhiro Yokoyama 2002

The computational complexity of determining if a given monic irreducible polynomial over the integers $\mathbb{Z}$, is soluble by radicals is in $\mathbb{P}$ Ref "Solvability by Radicals Is in Polynomial Time", S. Landau G.L Miller 1984

A survey of recent "Techniques for the Computation of Galois Groups", Alexander Hulpke

Of course if one is looking for good approximation algorithms and their complexity (e.g Newton's method or Sturm's Theorem) this is a slightly different question and the already posted answer provides more infomation in that direction.

$\endgroup$
  • $\begingroup$ Thanks! Seems I have accidentally asked myself a very exciting question! $\endgroup$ – user6818 Apr 23 '15 at 16:24
  • $\begingroup$ @user6818, thanks updated answer with more information and further references $\endgroup$ – Nikos M. Apr 25 '15 at 17:09
11
$\begingroup$

I assume you are considering polynomials with integer coefficients.

You've taken the wrong starting point for your investigations; your goal is to find good estimates for the real roots. Looking for an algebraic formula so that you can evaluate it to enough precision is something you can do, but it's not really the right thing to do here. (unless, of course, "the k-th largest real root of a polynomial" is one of your algebraic operations)

A much better starting point is to use Sturm's theorem to isolate the roots of the polynomial. You can then produce better estimates by binary search, but if that's too slow, you can use Newton's method to quickly produce estimates of high precision.


But that's just about finding certificates. There's still the question of what certificates can exist.

First off, I will point out that you can directly compute whether or not two of the roots are exactly $k$ units apart, e.g. by computing $\gcd(p(x), p(x-k))$. You will also have to decide what you want to do about repeated roots and deal with appropriately. I assume you will deal with these case specially.

If we know the two roots are not exactly $k$ units apart, that means that you can produce an estimate of sufficient precision to prove that they are either greater or less than $k$ units apart. e.g. there are two kinds of certificates:

The first kind (proof in the negative) is

  • $a$ is not a root of $p$
  • $p$ has no roots in $(a-k, a)$
  • $p$ has three roots in $(a, \infty)$

The second kind (proof in the positive) is

  • $a$ is not a root of $p$
  • $p$ has at least two roots in $(a-k,a)$
  • $p$ has two roots in $(a, \infty)$

A certificate can be verified by using Sturm's theorem. Now, your question about the size of a certificate boils down to finding how many bits of precision you need to represent $a$.

In other words, what are the bounds on the possible values of $a-b-k$, where $a,b$ are roots of $f$?

I'm not sure of a great approach, but one that should give you something is to observe that all of these values are roots of the polynomial:

$$ g(x) = \mathop{\text{Res}_y}(f(y), f(x + y + k)) $$

Why? Recall that the resultant of two monic polynomials is the product of all differences of their roots, so

$$ g(x) = c^{d^2} \prod_{a,b}(b - (a - x - k)) = \prod_{a,b} (x - (a-b-k))$$

where $c$ is the leading coefficient and $d$ is the degree of $f$. (maybe I've written the formula for $-g(x)$ instead of $g(x)$; I'm never sure on the sign)

So the question is to find estimates for how large the coefficients $g$ can be, and then once you know that, find estimates to how close a root of $g$ can be to zero.

(or, alternatively, find the largest magnitude that a root of the reverse polynomial of $g$ can have; the roots of the reverse polynomial are the inverses of the roots of $g$)

$\endgroup$
  • 1
    $\begingroup$ Are there any issues about data representation, here? NP is fundamentally about Turing machines and it's not immediately obvious how that relates to real numbers or the number of bits required to write down rationals of sufficient precision. (I'm sorry to not be very constructive: I know enough to know this might be a problem but not enough to know whether it really is a problem or, if it is, how to resove it.) $\endgroup$ – David Richerby Apr 18 '15 at 15:30
  • $\begingroup$ @DavidRicherby: I'm assuming the inputs are essentially just the coefficients of the polynomial written in binary, and my expectation is that the number of bits you need to represent $a$ in binary will be bounded by a polynomial function of the number of bits of input. If we use two parameters, the number of bits of input and the degree of the polynomial, then I'm nearly certain that the number of bits you need for $a$ will be polynomial in the number of bits of input, but I'm less sure exactly how it will depend on the degree. $\endgroup$ – user5386 Apr 18 '15 at 15:37
  • $\begingroup$ The input as a list of coefficients makes perfect sense. But your assumptions about the precision needed to represent the roots definitely need to be checked. For example, the reason that Hilbert's tenth problem (solving Diophantine equations) is undecidable is essentially that you can't bound the length of the solution in terms of the length of the input. That's not directly applicable here, since we only have one variable and we're not looking for integer solutions, but it does ask a pretty big question about the assumption of boundedness. $\endgroup$ – David Richerby Apr 18 '15 at 16:02
  • 1
    $\begingroup$ @David: The theory of real closed fields is dramatically different than number theory; intuition about one doesn't really translate well to the other. $\endgroup$ – user5386 Apr 18 '15 at 16:31
  • $\begingroup$ What if two roots are $k+2^{-2^{2^n}}$ apart or $k-2^{-2^{2^n}}$ apart? Producing an estimate of sufficient precision can be hard. $\endgroup$ – Yuval Filmus Apr 18 '15 at 16:37
3
$\begingroup$

am going to take your questions as mostly open ended. the galois proof now known as the Abel-Ruffini thm shows the impossibility of polynomial solutions to the quintic. (in contrast to eg the quadratic equation). so its not really a result on the hardness of a problem per se but rather the impossibility. in this sense it is more analogous to eg a proof of undecidability of the halting problem. complexity theory is in general concerned with the "cost" of computing solutions. that is the viewpoint of two leading CS researchers in the introductory section of this following paper (Computability and Complexity / Kleinberg & Papadimitriou), sec 1 The Quest for the Quintic Formula:

Viewed from the safe distance of a few centuries, the story is clearly one about com- putation, and it contains many of the key ingredients that arise in later efforts to model computation: We take a computational process that we understand intuitively (solving an equation, in this case), formulate a precise model, and from the model derive some highly unexpected consequences about the computational power of the process. It is precisely this approach that we wish to apply to computation in general.

elsewhere a loose/ general analogy might be that a P$\neq$NP proof (or other complexity class separation) is analogous to a computational impossibility result somewhat like the Abel-Ruffini thm. a separation result says roughly that problems of a certain type cannot be solved with "computational resources" of another certain type. a P$\neq$NP theorem would be viewed as a (monumental) computational impossibility result.

$\endgroup$
  • $\begingroup$ I'm not sure that the halting problem is a good analogy, since it's more along the lines of "you can't compute the answer" rather than "there isn't an answer at all". $\endgroup$ – user5386 Apr 18 '15 at 21:56
  • $\begingroup$ Isn't Galois theorem a computational impossibility result just like the Halting problem? $\endgroup$ – user6818 Apr 18 '15 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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