Completeness and Reduction in Algebraic Complexity Theory
By: by Peter Bürgisser
Series: Algorithms and Computation in Mathematics -- 7; Algorithms and Computation in Mathematics -- 7
Publisher: Springer Berlin Heidelberg
Published: 2000
Place of publication: Berlin, Heidelberg
Language: eng
Format: [electronic resource] /
Number of pages: 168
ISBN-13: 9783642086045; 9783662041796
Subjects: Mathematics; Information theory; Computer science; Algebra
Description: The theory of NP-completeness is a cornerstone of computational complexity. This monograph provides a thorough and comprehensive treatment of this concept in the framework of algebraic complexity theory. Many of the results presented are new and published for the first time. Topics include: complete treatment of Valiant's algebraic theory of NP-completeness, interrelations with the classical theory as well as the Blum-Shub-Smale model of computation, questions of structural complexity, fast evaluation of representations of general linear groups, and complexity of immanants. The book can be used at the advanced undergraduate or at the beginning graduate level in either mathematics or computer science.
Notes: Online full text is restricted to subscribers.

Also available in print.

Mode of access: World Wide Web.
Table of contents: title: 1. Introduction; title: 2. Valiant's Algebraic Model of NP-Completeness; title: 3. Some Complete Families of Polynomials; title: 4. Cook's versus Valiant's Hypothesis; title: 5. The Structure of Valiant's Complexity Classes; title: 6. Fast Evaluation of Representations of General Linear Groups; title: 7. The Complexity of Immanants; title: 8. Separation Results and Future Directions; title: References; title: List of Notations; title: Index.