Introduction to the Theory of Computation

There is not too much to say about this spectacular textbook that has not been said already by many of the other reviewers. This is a wonderful presentation of key ideas in complexity, on that fulfills a big hole in the literature.The presentation is notable for its clarity. In exposition, the author chooses one important idea and carefully but clearly develops that single idea. By contrast, certain other textbook authors (who shall remain nameless) tend to try and present so many variants of the same idea that the reader gets bogged down and loses sight of the key elements.Michael Sipser, perhaps ironically, is known for some fiendishly complex proofs in complexity theory (e.g. Go is PSPACE hard). Despite that, the book is a model of clarity. Not surprisingly, the book really shines in its completeness presentation, where NP-completeness, PSPACE completeness, and the equivalence of IP and PSPACE are shown with great power and verve. Perhaps my only reservation is that the book is a bit light on the recursive hierarchy, but there's enough for the curious student. Also, lets face it, nowadays the custom is probably to have more pictures and color - a teacher might want to supplement some of the proofs with demos, or the enterprising student unfamiliar with the area could do so himself.Finally, the book has some superb special topics that make it a necessity and make most of the older theory of computation books entirely obsolete. There are great introductions to Interactive Proofs, Probabilistic Computing, Parallel Computing, and Information Theory. And nice nuances throughout, like the proof that P=NP is not relativization-independent.All in all, this is one of those very rare books that are written by a top practitioner and theorist on the one hand, yet at the same time are clear and well-motivated for the reader.Conclusion: presentation: terrific. Choice of topics: terrific. Writing style: terrific. Clarity: terrific. It's a great text.