Publication
Journal of Computer and System Sciences
Paper

Computational Complexity of Algebraic Functions

View publication

Abstract

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.

Date

Publication

Journal of Computer and System Sciences

Authors

Topics

Share