I used this book as a companion text for a graduate-level course in complexity theory last semester, and I found it quite useful. You should be warned, however, that this is not a standalone complexity textbook. Many of the basic theorems (such as the time and space hierarchy theorems) are skipped entirely, and most of the fundamental notions (such as DTIME, P, and NP) are presented briefly in the appendix and used freely throughout the book. Thus, this is no substitute for a general textbook on complexity theory.

There is a lot of beautiful and important material here, however, that is frequently omitted from general textbooks. Often, one really wants to cover some of this material in a graduate course, because the proofs introduce important techniques that graduate students should master. Conventional textbooks usually don’t get around to presenting these techniques.

The beauty of this book is its novel organization. Rather than organizing the book around different topic areas (time complexity, space complexity, circuits, and so on), the authors have chosen to have each chapter focus on a different technique. Each technique can then be used to prove useful theorems relating to several topics (such as time complexity, space complexity, and circuits). The approach is innovative and successful.

The titles of the nine chapters list the techniques that are presented:

(1) The Self-Reducibility Technique

(2) One-Way Function Technique

(3) The Tournament Divide and Conquer Technique

(4) The Isolation Technique

(5) The Witness Reduction Technique

(6) The Polynomial Interpolation Technique

(7) The Nonsolvable Group Technique

(8) The Random Restriction Technique

(9) The Polynomial Technique

On the whole, I found all of the chapters to be well written, with clear proofs that provide readers with good, intuitive explanations of what is going on. Most of the chapters do not depend on any other chapter, which allows for great flexibility in selecting topics to cover in a class.

No book is perfect, of course. The authors do not provide exercises. They have included some topics that seem less important to me than some that they left out. In chapter 1, after the authors present some warm-up theorems leading up to Mahaney’s theorem, they choose not to present a very simple proof of Mahaney’s theorem, and instead prove a more general theorem which necessarily requires a more complex proof. In chapter 8, I would have preferred that the authors use a different approach in proving the switching lemma.

But these are minor quibbles. On the whole, I found it very useful to be able to assign readings from this text, and the students found the book quite helpful. They especially liked the appendices “A Rogues’ Gallery of Complexity Classes” and “A Rogues’ Gallery of Reductions.” These serve as good road maps through the wilderness of names and notation that otherwise can se em daunting (UP, #P, LOGCFL, SPP, and so forth). These appendices also contain excellent pointers to the complexity literature for those seeking additional details.

As with any book, there are errata. The authors maintain a list of typographical errors on their home pages at the University of Rochester.

I recommend this book as a supplementary textbook for graduate-level classes, and as a reference for anyone interested in computational complexity theory.