98d:68109 68Q40 (68Q25)
Bürgisser, Peter(CH-ZRCH); Clausen, Michael(D-BONN)
Algebraische Komplexitätstheorie. I. Eine Einführung. (German. German summary) [Algebraic complexity theory. I. An introduction]
Sém. Lothar. Combin. 36 (1996), Art. S36a, approx. 18pp. (electronic).

This is an introduction to algebraic complexity theory. It introduces and motivates the various measures of complexity for the computation of polynomials with coefficients in a field using the operations addition, subtraction, multiplication, and division. It presents sharp complexity bounds for the number of nonscalar operations. Theorem [V. Strassen, Numer. Math. 20 (1972/73), 238--251; MR 48 #3296]: The number of nonscalar operations in any computation of arbitrary polynomials $f\sb 1,\cdots,f\sb m\in k(X\sb 1,\cdots,X\sb n)$ is at least $\log\deg(f\sb 1,\cdots,f\sb m)$ where $\deg(f\sb 1,\cdots, f\sb m)$ is the geometrical degree of the graph associated with the polynomial functions $f\sb 1,\cdots,f\sb m$.

Also presented is the analysis of the Euclidean algorithm for univariate polynomials with coefficients in a field due to Schonhage, Knuth and Strassen. Lower and upper bounds for the nonscalar complexity of the sequence of polynomials $A\sb i$ occurring in the standard Euclidean algorithm are proportional to $n·H(d)$, where $H(d)=-\sum\sb {d\sb i>0}(d\sb i/n)\log(d\sb i/n)$ is the entropy of the degrees $d\sb i$ of the $A\sb i$ and $n$ the maximal degree of the input polynomials. Also presented is the lower bound for algebraic computation trees using Betti-numbers according to M. Ben-Or [in Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 80--86, ACM, New York, 1983; see MR 87g:68004]. No proofs are given.

\{For Part II see the following review [MR 98d:68110].\}

Reviewed by Claus-Peter Schnorr

Cited in: 98h:68124 98d:68110

Back