Buch, Englisch, 168 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 970 g
Buch, Englisch, 168 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 970 g
Reihe: Algorithms and Computation in Mathematics
ISBN: 978-3-540-66752-0
Verlag: Springer
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.
Fachgebiete
- Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
- Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
- Mathematik | Informatik Mathematik Algebra
- Mathematik | Informatik EDV | Informatik Informatik Berechenbarkeitstheorie, Komplexitätstheorie
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.
