Completeness and Reduction in Algebraic Complexity Theory
One of the most important and successful theories in computational complex ity is that of NP-completeness. This discrete theory is based on the Turing machine model and achieves a classification of discrete computational prob lems according to their algorithmic difficulty. Turing machines formaliz...
| Main Author: | |
|---|---|
| Format: | eBook |
| Language: | English |
| Published: |
Berlin, Heidelberg
Springer Berlin Heidelberg
2000, 2000
|
| Edition: | 1st ed. 2000 |
| Series: | Algorithms and Computation in Mathematics
|
| Subjects: | |
| Online Access: | |
| Collection: | Springer Book Archives -2004 - Collection details see MPG.ReNa |
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