Computational Complexity of Algebraic Functions
We consider algebraic functions that are rational functions of roots (of various degrees) of rational functions of indeterminates. We associate a cost C(d) with the extraction of a dth root and assume that C satisfies certain natural axioms. We show that the minimum cost of computing a finite set of algebraic functions of the form considered is C(d1) + … + C(dr), where d1…dr are the torsion orders of the Galois group of the extension generated by the functions.
© 1981 Elsevier Ltd.
Nicholas Pippenger, Computational Complexity of Algebraic Functions, Journal of Computer and System Sciences, Volume 22, Issue 3, June 1981, Pages 454-470, ISSN 0022-0000, 10.1016/0022-0000(81)90043-X. (http://www.sciencedirect.com/science/article/pii/002200008190043X)