E-Book, Englisch, Band 7, 168 Seiten, eBook
Bürgisser Completeness and Reduction in Algebraic Complexity Theory
2000
ISBN: 978-3-662-04179-6
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
E-Book, Englisch, Band 7, 168 Seiten, eBook
Reihe: Algorithms and Computation in Mathematics
ISBN: 978-3-662-04179-6
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark
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.
Zielgruppe
Research
Autoren/Hrsg.
Weitere Infos & Material
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.
