Computational Complexity in Algebraic Function Fields
Document Type
Conference Proceeding
Department
Mathematics (HMC)
Publication Date
10-1979
Abstract
The problem solved in this paper is the following. Let x1, ..., xn be indeterminates; let r1, ..., rk be simple radicals, by which is meant let r1, ..., rk be the square roots of rational functions of x1, ..., xn; and let f1, ..., fm be simple algebraic functions, by which is meant let f1, ..., fm be rational functions of r1, ..., rk and x1, ..., xn. What is the minimum possible cost of computing f1, ..., fm from x1, ..., xn, if rational operators have cost zero and square root extractions (the only irrational operations allowed) have cost one?
Rights Information
© 1979 IEEE
DOI
10.1109/SFCS.1979.11
Recommended Citation
Pippenger, Nicholas. "Computational Complexity in Algebraic Function Fields", IEEE Symp. on Foundations of Comp. Sci., 20 (1979), 61-65.
