Completeness and reduction in algebraic complexity theory
Author(s)
Bibliographic Information
Completeness and reduction in algebraic complexity theory
（Algorithms and computation in mathematics, v. 7）
Springer, 2010
- : pbk
Available at / 2 libraries
-
No Libraries matched.
- Remove all filters.
Note
Bibliography: p. [149]-157
Includes index
Description and Table of Contents
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.
Table of Contents
1 Introduction.- 2 Valiant's Algebraic Model of NP-Completeness.- 3 Some Complete Families of Polynomials.- 4 Cook's versus Valiant's Hypothesis.- 5 The Structure of Valiant's Complexity Classes.- 6 Fast Evaluation of Representations of General Linear Groups.- 7 The Complexity of Immanants.- 8 Separation Results and Future Directions.- References.- List of Notation.
by "Nielsen BookData"
