Cover Image

Completeness and Reduction in Algebraic Complexity Theory /

Show other versions (1)

The theory of NP-completeness is a cornerstone of computational complexity. This monograph provides a thorough and comprehensive treatment of this concept in the framework of algebraic complexity theory. Many of the results presented are new and published for the first time. Topics include: complete...

Full description

Bibliographic Details
Main Author: Bürgisser, Peter
Corporate Author: SpringerLink (Online service)
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2000.
Series:Algorithms and computation in mathematics ; 7.
Subjects:
Mathematics.
Information theory.
Algebra.
Computer science > Mathematics.
Electronic books.
Online Access:Connect to the full text of this electronic book
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 Notations
  • Index.