Computational Complexity in Algebraic Function Fields
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?
© 1979 IEEE
Pippenger, Nicholas. "Computational Complexity in Algebraic Function Fields", IEEE Symp. on Foundations of Comp. Sci., 20 (1979), 61-65.