Completeness and Reduction in Algebraic Complexity Theory (Algorithms and Computation in Mathematics, 7) - Hardcover

Bürgisser, Peter

Hardcover

ISBN 10: 3540667520 ISBN 13: 9783540667520

Publisher: Springer, 2000

Synopsis

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.

About this title

Review

".... 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

 

Edition details

• Publisher: Springer
• Publication date: 2000
• ISBN 10: 3540667520
• ISBN 13: 9783540667520
• Binding: Hardcover
• Language: English
• Number of pages: 180