+- MKLab (https://mklab.gr)
+-- Forum: [INDEX] (https://mklab.gr/forumdisplay.php?fid=1)
+--- Forum: COMPUTATIONS (https://mklab.gr/forumdisplay.php?fid=4)
+---- Forum: PROGRAMMING (https://mklab.gr/forumdisplay.php?fid=68)
+----- Forum: BOOKS (https://mklab.gr/forumdisplay.php?fid=69)
+----- Thread: The Nature of Computation [Moore] (/showthread.php?tid=1814)
The Nature of Computation [Moore] - mklabgr - 09-03-2026
? The Nature of Computation
Book name:The Nature of Computation
Authors: Cristopher Moore & Stephan Mertens
Publication date: 11 August 2011
Publisher: Oxford University Press
ISBN: 978-0-19-923321-2 (OUP Academic)
Summary
The Nature of Computation is a broad and unusually accessible introduction to theoretical computer science and computational complexity, written from a strongly mathematical perspective. Moore and Mertens aim to explain not merely how algorithms work, but what computation itself can and cannot accomplish. A central theme is the distinction between problems that can be solved efficiently and those for which finding a solution appears intrinsically difficult. This naturally leads to the classes P and NP, NP-completeness, reductions, and the famous unresolved question $P=NP?$ The authors deliberately minimize unnecessary formalism while retaining the mathematical ideas behind the theory.
The book begins with fundamental algorithms and techniques such as recursion, divide-and-conquer, dynamic programming, greedy algorithms, shortest paths, and reductions. It then moves into increasingly sophisticated areas: NP-completeness, optimization and approximation algorithms, randomized computation, interactive proofs, pseudorandomness, random walks and Markov chains. A distinctive feature is the connection between computation and statistical physics: the authors examine counting and sampling problems and show how concepts such as phase transitions can arise in difficult computational problems.
The final portions extend the discussion to the limits and alternative models of computation, most notably quantum computing. Rather than treating complexity theory as an isolated branch of computer science, Moore and Mertens connect it with mathematics, physics, biology, networks, probability, and optimization. The result is a substantial book—containing roughly 900 problems and exercises and 370 figures—that can function both as an advanced textbook and as a conceptual tour of modern complexity theory. It is particularly suitable for mathematically mature undergraduate or graduate students, physicists and mathematicians interested in computation, and computer scientists wanting a deeper conceptual view of their field.
Key takeaways
- Computational complexity asks not only whether a problem can be solved, but how many computational resources are required to solve it.
- $P$ vs. $NP$ forms the conceptual heart of the book, with NP-completeness and reductions explaining why apparently unrelated difficult problems are deeply connected.
- The book goes well beyond classical complexity theory, covering randomized algorithms, interactive proofs, pseudorandomness, approximation, Markov chains and quantum computation.
- One of its most interesting features is the link between computation and statistical physics, particularly the appearance of phase-transition-like phenomena in NP-complete problems.
- Despite its depth, the authors intentionally emphasize intuition and explanation over excessive formalism, making difficult ideas more approachable than in many standard complexity-theory texts.
BOOK