Bürgisser, a top expert on algebraic complexity theory, has written a monograph on current research in this field. This book gives new results in the theory of NP-completeness. It is written for mathematicians and computer scientists on both research and graduate level.

Only monograph with the latest results in the field. Includes supplementary material: sn.pub/extras

Autorentext

Peter Bürgisser is an internationally recognized expert in complexity theory. He is associate editor of the journal Computational Complexity and he was invited speaker at the 2010 International Congress Mathematicians. Felipe Cucker is well known for his work on complexity over the real numbers, jointly with L. Blum, S. Smale and M. Shub. He also worked in learning theory and made seminal contributions to condition numbers in optimization and their probabilistic analyses. F.C. is former chair of the Society for the Foundations of Computational Mathematics and the current managing editor of the society's journal.

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