Computational Complexity of Algebraic Functions

Document Type



Mathematics (HMC)

Publication Date



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 d1dr are the torsion orders of the Galois group of the extension generated by the functions.

Rights Information

© 1981 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.