Completeness and Reduction in Algebraic Complexity Theory |
|
| Author:
| Bürgisser, Peter |
| Editor:
| Becker, E.
Bronstein, M.
Cohen, H.
Eisenbud, David
Gilman, R. |
| Series title: | Algorithms and Computation in Mathematics Ser. |
| ISBN: | 978-3-540-66752-0 |
| Publication Date: | Jun 2000 |
| Publisher: | Springer Berlin / Heidelberg
|
| Imprint: | Springer |
| Book Format: | Hardback |
| List Price: | USD $109.99 |
Book Description:
|
This is a thorough and comprehensive treatment of the theory of NP-completeness in the framework of algebraic complexity theory. Coverage includes 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.
This is a thorough and comprehensive treatment of the theory of NP-completeness in the framework of algebraic complexity theory. Coverage includes 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.