Computational Complexity of Algebraic Functions

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1981

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(d₁) + … + C(d_r), where d₁…d_r 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.

DOI

10.1016/0022-0000(81)90043-X

Recommended Citation

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)