[Solved]: Is there a complexity viewpoint of Galois' theorem?

Problem Detail: 

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

Asked By : user6818

Answered By : Nikos M.

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.

Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents