Algebraic complexity theory. With the collaboration of Thomas Lickteig.

*(English)*Zbl 1087.68568
Grundlehren der Mathematischen Wissenschaften 315. Berlin: Springer (ISBN 3-540-60582-7/hbk). xxiii, 618 p. (1997).

Within the general theory of computational complexity, algebraic complexity theory can be distinguished by the source of its problems (algebra) and by its stress on symbolic (as opposed to numerical) aspects in computational models. Among others, the book discusses the following fundamental problems: multiplication of polynomials; multiplication, inversion and composition of power series; computing the greatest common divisor of polynomials; polynomial interpolation and evaluation of polynomials; matrix multiplication; inversion and other problems of (bi)linear algebra. The main computational models are the straight-line program and the computation tree.

The authors stress that there is a difference between algebraic complexity and computer algebra. The book emphasizes proving lower bounds on complexity, that is, proving that a given problem cannot be solved faster than in a particular time. On the other hand, computer algebra deals with upper bounds on complexity for algorithmic problems in algebra. Naturally, proving a good upper bound reduces to constructing an efficient algorithm. Proving a nontrivial lower bound may turn out to be quite difficult and often requires an advanced technique even if the problem is “elementary” and the bound looks “obvious”.

The book consists of five parts: 1. Fundamental algorithms, 2. Elementary lower bounds, 3. High degree, 4. Low degree, 5. Complete problems. The first part discusses efficient algorithms for various problems involving polynomials as well as interesting results on Vapnik-Chervonenkis dimension from information theory. In particular, a result by Meyer auf der Heide on a “nonuniform polynomial time” algorithm for an NP-complete problem serves as a caveat that sometimes our intuition regarding lower complexity bounds is wrong. Part 2 introduces the two computational models (straight-line programs and computation trees) used throughout the book. It contains transcendence degree arguments and other techniques, which, in particular, allow one to prove optimality of Horner’s rule. Part 3 employs topological tools (Betti numbers and the degree of a map) to produce nontrivial lower complexity bounds. In particular, the fundamental problem of testing the membership of a given point \(x \in \mathbb{R}^n\) in a given semi-algebraic set \(V \subset \mathbb{R}^n\) is considered. The authors explain how the Betti numbers of \(V\) provide a lower complexity bound for this problem, discuss applications to computational geometry and mention some recent advances: what if \(V\) is homologically trivial, but has a nontrivial differential structure, for example, \(V\) is a polyhedron? There has been recent substantial progress in this area, relating computational complexity with singularities [see D. Grigoriev, M. Karpinski and N. Vorobjov, Discrete Comput. Geom. 17, 191–215 (1997; Zbl 0871.68176)]. Part 4 deals mostly with bilinear complexity, that is, the computational complexity of bilinear maps. The central topic is matrix multiplication and the notion of tensor rank. The authors discuss the complexity of fundamental problems of linear algebra such as matrix inversion, transformation to echelon form, computing the characteristic polynomial, computing a basis for the kernel, and finding the \(LUP\) decomposition. Lower bounds for the multiplicative complexity of algebras are also discussed. An advanced technique for estimating the rank of particular tensors as well as of generic tensors is presented. The book describes interesting connections between bilinear complexity over finite fields and codes. Part 5 presents a theory due to L. Valiant of reducibility and complexity classes for algebraic problems. The universal role of the permanent and determinant in algebraic complexity is discussed.

The book contains interesting exercises and useful bibliographical notes. In short, this is a nice book.

The authors stress that there is a difference between algebraic complexity and computer algebra. The book emphasizes proving lower bounds on complexity, that is, proving that a given problem cannot be solved faster than in a particular time. On the other hand, computer algebra deals with upper bounds on complexity for algorithmic problems in algebra. Naturally, proving a good upper bound reduces to constructing an efficient algorithm. Proving a nontrivial lower bound may turn out to be quite difficult and often requires an advanced technique even if the problem is “elementary” and the bound looks “obvious”.

The book consists of five parts: 1. Fundamental algorithms, 2. Elementary lower bounds, 3. High degree, 4. Low degree, 5. Complete problems. The first part discusses efficient algorithms for various problems involving polynomials as well as interesting results on Vapnik-Chervonenkis dimension from information theory. In particular, a result by Meyer auf der Heide on a “nonuniform polynomial time” algorithm for an NP-complete problem serves as a caveat that sometimes our intuition regarding lower complexity bounds is wrong. Part 2 introduces the two computational models (straight-line programs and computation trees) used throughout the book. It contains transcendence degree arguments and other techniques, which, in particular, allow one to prove optimality of Horner’s rule. Part 3 employs topological tools (Betti numbers and the degree of a map) to produce nontrivial lower complexity bounds. In particular, the fundamental problem of testing the membership of a given point \(x \in \mathbb{R}^n\) in a given semi-algebraic set \(V \subset \mathbb{R}^n\) is considered. The authors explain how the Betti numbers of \(V\) provide a lower complexity bound for this problem, discuss applications to computational geometry and mention some recent advances: what if \(V\) is homologically trivial, but has a nontrivial differential structure, for example, \(V\) is a polyhedron? There has been recent substantial progress in this area, relating computational complexity with singularities [see D. Grigoriev, M. Karpinski and N. Vorobjov, Discrete Comput. Geom. 17, 191–215 (1997; Zbl 0871.68176)]. Part 4 deals mostly with bilinear complexity, that is, the computational complexity of bilinear maps. The central topic is matrix multiplication and the notion of tensor rank. The authors discuss the complexity of fundamental problems of linear algebra such as matrix inversion, transformation to echelon form, computing the characteristic polynomial, computing a basis for the kernel, and finding the \(LUP\) decomposition. Lower bounds for the multiplicative complexity of algebras are also discussed. An advanced technique for estimating the rank of particular tensors as well as of generic tensors is presented. The book describes interesting connections between bilinear complexity over finite fields and codes. Part 5 presents a theory due to L. Valiant of reducibility and complexity classes for algebraic problems. The universal role of the permanent and determinant in algebraic complexity is discussed.

The book contains interesting exercises and useful bibliographical notes. In short, this is a nice book.

##### MSC:

68Q25 | Analysis of algorithms and problem complexity |

68W30 | Symbolic computation and algebraic computation |

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |

68Q05 | Models of computation (Turing machines, etc.) (MSC2010) |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |

11Y16 | Number-theoretic algorithms; complexity |

12Y05 | Computational aspects of field theory and polynomials (MSC2010) |