The Nature of Computation: Book Review

Book Review by Haris Aziz of


The Nature of Computation
by Cristopher Moore and Stephan Mertens Oxford University Press, 2011
985 pages, Hardcover




The Nature of Computation (TNoC) is a comprehensive, accessible, and highly enjoyable book that conveys the key intellectual contributions of the theory of computing. The project took off as an effort to present theoretical computer science to physicists but it is as suitable for any science graduate who is curious to explore beautiful and deep ideas related to the mathematical structure of problems. Moore and Mertens explain the essence of the book as follows:
“It is a question about the mathematical structures of problems, and how these struc- tures help us solve problems or frustrate our attempts to do so. This leads us, in turn, to questions about the nature of mathematical proof, and even of intelligence and cre- ativity.”
TNoC not just provides a window so that people from other disciplines can get glimpses of the interesting nuggets from computer science but provides an entertaining open house session where a visitor can visit various deep ideas and understand the core arguments behind key results.

Summary
TNoC is divided into fifteen chapters.


1. Prologue
2. The Basics
3. Insights and Algorithms
4. Needles in a Haystack: the Class NP
5. Who is the Hardest One of All? NP-Completeness 6. The Deep Question: P vs. NP
7. The Grand Unified Theory of Computation
8. Memory, Paths, and Games
1
10. Randomized Algorithms
11. Interaction and Pseudorandomness
12. Random Walks and Rapid Mixing
13. Counting, Sampling, and Statistical Physics
14. When Formulas Freeze: Phase Transitions in Computation 15. Quantum Computation
Appendix Mathematical Tools


The book starts with a beautiful narrative on how the problems of finding an Eulerian cycle and a Hamiltonian cycle are apparently similar but have different complexity. It discusses various com- plexity classes, approximation algorithms, complexity of counting and sampling, phase transitions etc.

Chapters 1 to 5 consider more traditional topics in algorithms and complexity. The focus of the earlier chapters is on running time analysis, classical algorithmic techniques, and time complexity classes. In particular, Chapter 3 is a one-stop algorithms primer with explanations on dynamic programming and network flows. Chapter 4, 5 and 6 cover NP-completeness, provide intuition why NP-complete problems are hard, and discusses importance of the ‘P vs NP question’ in detail.

Chapter 7 covers topics including the halting problem, decidability, and the Church-Turing Thesis. Chapter 8 focuses on issues around space complexity with explanations of complexity classes such as L, NL, and PSPACE. Chapter 9 is a very readable and insightful chapter capturing fundamental topics mathematical programming including inapproximability, duality, interior point methods, and semidefinite programming.

There is great coverage of the role of randomization in computation especially in Chapters 10, 11, 12, and 13. Chapter 10 provides a taste of randomized algorithms with a deeper study of the nature of primes and randomized algorithms for testing whether a number is a prime. Chapter 11 discusses zero-knowledge proofs and presents the PCP theorem that essentially shows that problems in NP have proofs that can be checked by looking at a few bits. In Chapter 11, derandomization is also discussed. Chapter 12 takes the reader on a wonderful random walk tour. The chapter builds the ground so that ideas about rapidly maxing Markov chains are applied to counting problems in Chapter 13.

Chapter 14 covers the intriguing phenomenon of phase transitions: problems that almost always have yes instances end up having almost always no instances when the number of constraints per variable crosses a critical threshold. The authors’ background in physics is valuable in giving further insights. The book concludes with Chapter 15 — one of the most elegant introductions on quantum computation.

Any reader with some college mathematics background will be able to appreciate the manner in which fundamental algorithmic techniques such as recursion, divide and conquer, dynamic pro- gramming and network flows are introduced and explained. Various other ideas on complexity classes are presented in a similar vein.

Opinion

It is difficult to understand what category one can put TNoC in. The first impression when one picks the book is how hefty it is. Built like an handbook or encyclopaedia, TNoC is indeed a labour of love of Merterns and Moore. Unike a typical encyclopaedia, TNoC focusses on the big ideas and covers them in a gentle and passionate manner. The book is also far removed from a typical textbook which would normally have a series of definitions and theorems. In fact, there is negligible formalism or formal notation. Despite the lack of formalism, TNoC is also not a fuzzy popular science book that is so generic that deep ideas cannot be conveyed. On the contrary, Moore and Mertens communicate ideas in a highly accessible way. The style of writing is very conversational. Without sounding overly serious, the authors manage to convey the beauty of very deep ideas and concepts from computer science.

Since TNoC is written in such a reader-friendly manner, it is a valuable resource for any ed- ucator. For so many ideas, my reaction was “this is a great way to explain this idea to a peer or a student.” The text is generously complemented with suitable figures and tables. The main arguments of numerous interesting results are provided. For example, I enjoyed the explanation of the connection between complexity of counting and sampling. There are exercises in the main text of each chapter and well-chosen exercise questions at the end of each chapter.

Each chapter includes historical notes that help give a sense of how important ideas were developed. The notes make the book a pleasure to read. For example, in the chapter on Counting, Sampling, and Statistical Physics, one finds the following note:

The class #P and the original proof that PERMANENT is #P-complete are due to Leslie Valiant [786, 787], who won the 2010 Turing Award for this and other work. The proof of PERMANENT’s #P-completeness that we give here is by Ben-Dor and Halevi [98]. Another simple proof, which reduces from #VERTEX COVERS, appears in Kozen [493]. Parsimonious reductions between NP-complete problems were also considered by Simon [739].

The text is interspersed by quote gems by people like George Polya, Stephen Kleene, Alan Turing, Jack Edmonds, Donald Knuth, Richard Bellman, Richard Feynman, David Hilbert and Richard Hamming. Philosophers make an entry as well with quotes by Plato and Nietzsche. Both the historical notes and quotes provide a nice context for the big ideas in theoretical computer science.
TNoC is refreshingly modern. Apart from ideas that are communicated in various classical texts, there are nice descriptions of relatively newer ideas such as the PPAD complexity class and the unique games conjecture.

The text is laced with charm and humor. In a section on hash functions, it was amusing to find a quote from a book by the delightful P. G. Wodehouse: “Heavens, Ginger! There must be something in this world that you wouldnt make a hash of.” The authors are self-deprecating at various places. For example, in the section on quantum computation, they make fun of physicists’ sense of humour at their naming of the “bra-ket” notation for describing quantum states ⟨φ | ψ⟩.

The authors also write that “Overall, we have endeavoured to write our book with the accessibility of Martin Gardner, the playfulness of Douglas Hofstadter, and the lyricism of Vladimir Nabokov. We have almost certainly failed on all three counts.” I beg to disagree!