Buch, Englisch, 168 Seiten, Previously published in hardcover, Format (B × H): 156 mm x 234 mm, Gewicht: 289 g
Buch, Englisch, 168 Seiten, Previously published in hardcover, Format (B × H): 156 mm x 234 mm, Gewicht: 289 g
Reihe: Algorithms and Computation in Mathematics
ISBN: 978-3-642-08604-5
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 Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
- Mathematik | Informatik EDV | Informatik Informatik Berechenbarkeitstheorie, Komplexitätstheorie
- Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
- Mathematik | Informatik Mathematik Algebra
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.
