Your cart is empty.

68W30 Computer science -- Algorithms -- Symbolic computation and algebraic computation

68Q05 Computer science -- Theory of computing -- Models of computation (Turing machines, etc.)

68Q15 Computer science -- Theory of computing -- Complexity classes (hierarchies, relations among complexity classes, etc.)

12Y05 Field theory and polynomials -- Computational aspects of field theory and polynomials -- Computational aspects of field theory and polynomials En-ligne: Springerlink | Zentralblatt | MathSciNet

No physical items for this record

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''. ... (MathSciNet)

There are no comments for this item.