Computational Complexity in Algebraic Function Fields

Document Type

Conference Proceeding


Mathematics (HMC)

Publication Date



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