Completeness and Reduction in Algebraic Complexity Theory

AvPeter Bürgisser

Inbunden, Engelska, 2000

Del i serien Algorithms and Computation in Mathematics

1 061 kr

Beställningsvara. Skickas inom 10-15 vardagar. Fri frakt över 249 kr.

Fler format och utgåvor

Häftad

1 061 kr

Beskrivning

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 treatment of 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.The book can be used at the advanced undergraduate or at the beginning graduate level in either mathematics or computer science.

Produktinformation

Utgivningsdatum:2000-06-21
Mått:155 x 235 x undefined mm
Format:Inbunden
Språk:Engelska
Serie:Algorithms and Computation in Mathematics
Antal sidor:168
Förlag:Springer-Verlag Berlin and Heidelberg GmbH & Co. KG
ISBN:9783540667520

Utforska kategorier

Recensioner i media

"... The subject matter of the book is not easy, since it involves prerequisites from several areas, among them complexity theory, combinatorics, analytic number theory, and representations of symmetric and general linear groups. But the author goes to great lengths to motivate his results, to put them into perspective, and to explain the proofs carefully. In summary, this monograph advances its area of algebraic complexity theory, and is a must for people for working on this subject. And it is a pleasure to read." Joachim von zur Gathen, Mathematical Reviews, Issue 2001g

Innehållsförteckning

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.