Seminar by Mr. Piyush P Kurur
Generalising Landu-Miller Solvability Test
Mr. Piyush P Kurur
Institute of Mathematical Sciences Chennai Date: Tue, April 12, 2005 Time: 3:45 PM Venue: CS-101
Abstract
Given a polynomial f(X) in Q(X), a classical problem is to check whether it is solvable by radicals. The celebrated theorem of Galois says that f(X) is solvable by radicals if and only if it has a solvable Galois group. Algorithmically this gave an exponential time algorithm because till date the only algorithm to compute the Galois group takes exponential time (and space). Landau and Miller in their beautiful work gave a polynomial time algorithm for this task. In this talk we generalise their result and show that for a polynomial f(X) in Q(X), checking whether its Galois group is in the family Gamma_d of groups, for bounded d, can be done in polynomial time. The family of groups Gamma_d arise naturally in various permutation group algorithms.