Hemaspaandra L.A., Ogihara M. The Complexity Theory Companion

Springer, 2002. — 378 p.We intend this book as a companion far students and professionals who seek an accessible, algorithmically oriented, research-centered, up-to-date guide to some of the most interesting techniques of complexity theory. The authors and their colleague Joel Seiferas have test-driven the book's approach in two different courses at the University of Rochester. We have used this technique- based approach in Rochester's one-semester basic complexity theory course, which is taken by all first-year computer science graduate students and also by those undergraduates specializing or specially interested in theoretical computer science, and in our second course on complexity theory, which is taken by all second-year graduate students as their theory "breadth" course.
We found in both these course settings that the technique-based approach allowed us to impart to students a significant amount of the feel and experience of complexity theory research and led to more student interest and involvement than occurred in earlier course incarnations using other texts.
We expect that this will not only benefit the complexity theory students in the courses, but will also help all the course's students become prepared to do work that is theoretically aware, informed, and well-grounded. At times, we stop the flow of a proof or discussion with a "Pause to Ponder." These are places at which we encourage the reader to pause for a moment and find his or her own solution to the issue raised. Even an unsuccessful attempt to craft a solution will usually make the proof/discussion that follows clearer and more valuable, as the reader will better understand the challenges posed by the hurdle that the proof/discussion overcomes.
With some exceptions due to result dependencies, the non-appendix chapters are generally ordered to put the easier chapters near the start of the book and the more demanding chapters near the end of the book.The Self-Reducibility Technique
The One-Way Function Technique
The Tournament Divide and Conquer Techniqu
The Isolation Technique
The Witness Reduction Technique
The Polynomial Interpolation Technique
The Nonsolvable Group Technique
The Random Restriction Technique
The Polynomial Technique
A Rogues' Gallery of Complexity Classes
A Rogues' Gallery of Reductions