Every computer scientist should know the basic tenets of computability theory and computational complexity theory--this is why introductory courses on these two fields are quite standard. Consequently, there are several textbooks that serve such courses. The book under review is now in its second edition, which already proves that it hits its mark.
The book is intended as an introductory text for a general audience of graduate computer science students. It can be viewed as being structured into three modules; the first two modules (which formed the first edition) contain basic material in computability and complexity theory. The first module (chapters 1 through 3) is dedicated to Turing machines, Church’s thesis, decidable and undecidable problems, the halting problem, the smn theorem, and the recursion theorem. The second module (chapters 4 through 7) covers the basic concepts and facts of computational complexity theory. Chapters 4 and 5 discuss linear compression and speed-up, hierarchy theorems for space and time (deterministic and nondeterministic), translation techniques, and relations among complexity classes. Chapters 6 and 7 offer a treatment of the basic complexity classes: polynomial time (P), nondeterministic polynomial time (NP), polynomial space (PSPACE), exponential time (EXP), and logarithmic space (LOGSPACE). The Cook-Levin theorem stating the NP-completeness of the satisfiability problem is proved. Two classical reductions showing that the vertex cover and clique are NP-complete are presented. The polynomial hierarchy is described, and complete problems for PSPACE, EXP, P, and LOGSPACE are given.
As mentioned, this is the book’s second edition. The main difference between it and the first edition comes from the massive amount of new material that the authors have included by adding five new chapters (chapters 8 through 12). The new material constitutes the third module, which is devoted to more advanced material in computational complexity. As the authors put it, this is justified because a graduate text, even an introductory one, “should be scholarly.” Chapter 8 deals with nonuniformity: Boolean circuits, advice classes, and the Karp-Lipton theorem. Chapter 9 studies alternating Turing machines and uniform circuit classes, especially NC. Chapter 10 presents the fundamental probabilistic complexity classes probabilistic polynomial time (PP), bounded-error probabilistic polynomial time (BPP), and randomized polynomial time (RP). It shows that the graph isomorphism problem is in the BP·NP class, and it explains why this represents strong evidence that this problem is not NP-complete. Chapter 11 presents counting complexity classes, the Valiant-Vazirani theorem, and Toda’s theorem. Chapter 12 is on interactive proof systems. It presents Arthur-Merlin games and includes a proof of the equality interactive polynomial time (IP) = PSPACE.
It should be emphasized that in spite of some inherent overlap with other good textbooks on computability and computational complexity, this book has its own personality. The authors are prominent researchers in complexity and the choice of topics (for example, the heavier weight to results in structural complexity) reflects their work and tastes. The coverage is self-contained and the writing is precise and elegant. Students will benefit from this book; they will not only learn the concepts, but also gain an appreciation for the depth and beauty of the field.
