If there were an encyclopedia of computational complexity, this would be the first--and perhaps only necessary--volume. The book contains more than 900 pages and covers a large number of deeply related subjects ranging from discrete mathematics to quantum computation.

The list of contents belongs to the field of computational complexity. The greatest value is that it is not a handbook of unrelated, very technical facts (the topic can quickly become very dense), but provides an extensive discussion about the subject. It proceeds from relatively traditional topics such as the complexity classes, the P versus NP question, and random walks to phase transitions, quantum computation, and the connections to pure math and physics. Several subsets of chapters can be used as a textbook for an undergraduate complexity course, and the book could easily cover two- or three-semester courses, with the more advanced topics perhaps suitable for graduate seminars.

Moore and Mertens took great care to think about the reader and included highlighted sections, examples, and exercises. Most important (and what makes it more valuable than other similar, although smaller, books) is that all of the math is wrapped within a context providing insights for both the mathematical and the nonmathematical reader.

Perhaps the only thing I can criticize is the title. The subject of the nature of computation is much larger than the subfield of computational complexity, although I acknowledge that this subfield is among the largest and most popular in theoretical computer science. I particularly enjoyed Section 7.6, “Computation Everywhere,” which discusses much of what I would have enjoyed to see further developed in the context of the ambitious title of the book.

The book is definitely delightful. Everyone interested in the topics it covers should get a copy.