The Complexity Theory Companion

The Complexity Theory Companion is an accessible, algorithmically oriented, research—centered, up—to—date guide to some of the most interesting techniques of complexity theory.

The book's thesis is that simple algorithms are at the heart of complexity theory. From the tree—pruning and interval—pruning algorithms that shape the first chapter to the query simulation procedures that dominate the last chapter, the central proof methods of the book are algorithmic. And to more clearly highligh...