Computation of algebraic functions with root extractions

We consider the problem of computing a set of algebraic functions that involve extracting roots of various degrees. We show that the complexity of computing a large class of algebraic functions is determined by the Galois group G of the extension generated by the functions. We relate the minimum cost to decomposing G into a sequence of normal subgroups such that each factor group is cyclic. We derive an exact answer for the case when the cost is logarithmic, while we provide upper and lower bounds for all the other cases. On the other hand, we develop a reasonably fast algorithm for the abelian case which has been already solved by Pippenger.