What do you think?
Rate this book
The Nature of Computation
Computational complexity is one of the most beautiful fields of modern mathematics, and it is increasingly relevant to other sciences ranging from physics to biology. But this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results like interactive proofs, cryptography, and quantum computing are usually considered too "advanced" to show to the typical student. The aim of this book is to bridge both gaps by explaining the deep ideas of theoretical computer science in a clear and enjoyable fashion, making them accessible to non computer scientists and to computer scientists who finally want to understand what their formalisms are actually telling.
This book gives a lucid and playful explanation of the field, starting with P and NP-completeness. The authors explain why the P vs. NP problem is so fundamental, and why it is so hard to resolve. They then lead the reader through the complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing.
At every turn, they use a minimum of formalism, providing explanations that are both deep and accessible. The book is intended for graduates and undergraduates, scientists from other areas who have long wanted to understand this subject, and experts who want to fall in love with this field all over again.
To request a copy of the Solutions Manual,
This book gives a lucid and playful explanation of the field, starting with P and NP-completeness. The authors explain why the P vs. NP problem is so fundamental, and why it is so hard to resolve. They then lead the reader through the complexity of mazes and games; optimization in theory and practice; randomized algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing.
At every turn, they use a minimum of formalism, providing explanations that are both deep and accessible. The book is intended for graduates and undergraduates, scientists from other areas who have long wanted to understand this subject, and experts who want to fall in love with this field all over again.
To request a copy of the Solutions Manual,
1032 pages, Hardcover
First published August 11, 2011
47 people are currently reading
1132 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 8 of 8 reviews
September 22, 2018
The most I can articulate so far (since I’m halfaway through the read) is that the mere existence of this volume is probably an invaluable accomplishment for the human consortium itself.
For the ostensibly unique concept, this book deserves a tier of its own kind – it is a pleasure to read, and I enjoy it in every single detail. It begins to acclimatate the reader by veering in a whirlwind excursus from Eulerian/Hamiltonian-paths, judiciously spangled with enthralling observations as insightful as handily they're delivered, to the brilliant sketching of phase transition of NP-completeness: stedily, cautious, more transparent than expected, with no sliding into arid minutiae. Then comes the realm of the real world applications of optimization problems; why linear programming turns out being NP-complete if solutions are required to be integers by some set of constraint, and from here on wide considerations on the satisfiability problems. The focus gradually moves around varius shades in the treatement of complexities classification, OR-related topics and further optimization task, led by the always excellent discussion of good examples.
I already gathered a helluva great deal from this work.
(And one of the best aspects, for me, is hands down the captivating manner the two SFI authors succeed to tying computational complexity to complex systems (yes, understood as in "nonlinear dynamical" systems) and statistical mechanics in such an effective way, with both the insistence on “time resources” and “spaces”, memory resurce, auxiliary resurce, as well as the high-quality approximation methods borrowed from physicist-approaches -- all this with a constant eye on random processes with respect to the physical import of “complexity”(I found myself much *less* interested in the quantum computing themes, though)).
Eminently satisfying is how the authors scrutinize the nexus betwen Kolmogorov complexity and information entropy, and so thermodynamics too – as the nontrivial analogy goes between “output”, “string-length”,..., and expected values of observable such as volume and energy as quantities.
So, well, all the goodies conjure up a case for this book to place itself as a unique specimen. That’s also how the 3/5-star should be temporarily taken as an upper limit – an exceeding 5, if you will (=6/10). However, the reason it does not bump to reach 10-tier (yet) seems, at least to me, that these massive 1000+ pages may ultimately make more of a competitive disadvantage than a ecstasy for a completist nerdish layman turned connisseuer of complexities. I guess this whole book will suffer bad in comparison with, like, the more prammatic Sipser or the Arora – Barak; at least if it’s computationality you’re looking for.
There’s plenty of reason why this should be seen as one of the most beautiful book out there on this topic, but - I fear - very little for it to be regarded as a good substitute for any of those. I’m, nonetheless, quite confident that after having made my way throught the end of the journey, the effort-justification will promptly kick in compelling me to heighten the scoring to the 10/10, A+.
For the ostensibly unique concept, this book deserves a tier of its own kind – it is a pleasure to read, and I enjoy it in every single detail. It begins to acclimatate the reader by veering in a whirlwind excursus from Eulerian/Hamiltonian-paths, judiciously spangled with enthralling observations as insightful as handily they're delivered, to the brilliant sketching of phase transition of NP-completeness: stedily, cautious, more transparent than expected, with no sliding into arid minutiae. Then comes the realm of the real world applications of optimization problems; why linear programming turns out being NP-complete if solutions are required to be integers by some set of constraint, and from here on wide considerations on the satisfiability problems. The focus gradually moves around varius shades in the treatement of complexities classification, OR-related topics and further optimization task, led by the always excellent discussion of good examples.
I already gathered a helluva great deal from this work.
(And one of the best aspects, for me, is hands down the captivating manner the two SFI authors succeed to tying computational complexity to complex systems (yes, understood as in "nonlinear dynamical" systems) and statistical mechanics in such an effective way, with both the insistence on “time resources” and “spaces”, memory resurce, auxiliary resurce, as well as the high-quality approximation methods borrowed from physicist-approaches -- all this with a constant eye on random processes with respect to the physical import of “complexity”(I found myself much *less* interested in the quantum computing themes, though)).
Eminently satisfying is how the authors scrutinize the nexus betwen Kolmogorov complexity and information entropy, and so thermodynamics too – as the nontrivial analogy goes between “output”, “string-length”,..., and expected values of observable such as volume and energy as quantities.
So, well, all the goodies conjure up a case for this book to place itself as a unique specimen. That’s also how the 3/5-star should be temporarily taken as an upper limit – an exceeding 5, if you will (=6/10). However, the reason it does not bump to reach 10-tier (yet) seems, at least to me, that these massive 1000+ pages may ultimately make more of a competitive disadvantage than a ecstasy for a completist nerdish layman turned connisseuer of complexities. I guess this whole book will suffer bad in comparison with, like, the more prammatic Sipser or the Arora – Barak; at least if it’s computationality you’re looking for.
There’s plenty of reason why this should be seen as one of the most beautiful book out there on this topic, but - I fear - very little for it to be regarded as a good substitute for any of those. I’m, nonetheless, quite confident that after having made my way throught the end of the journey, the effort-justification will promptly kick in compelling me to heighten the scoring to the 10/10, A+.
April 9, 2021
Really creative and fun. Definitely the most full of life book/semi-textbook on computational complexity. It's quite advanced and good for building intuition. Skims over lots of details so you probably want to read a more traditional intro to complexity alongside it or before it (Aurora/Sipser).
March 21, 2020
amazingly dense and excellent reference. For mere mortals like me it's impossible to read in its entirety, but I think it's a must for the bookshelf of anyone interested in the theory of computation at all.
January 11, 2020
A breathtakingly incredible work, but quite dense and not for the faint of heart.
March 17, 2025
Computation is not just a tool; it is an ontological principle—a framework that underpins the very fabric of logic, physics, and cognition. Moore and Mertens’ The Nature of Computation does not merely discuss algorithms and complexity; it unearths the fundamental limits of what can be known, what can be solved, and where mathematics itself begins to collapse under the weight of its own axioms.
This book operates at the intersection of computer science, mathematics, and physics, dissecting computational complexity not as a mere theoretical curiosity but as an unavoidable constraint on knowledge itself. NP-completeness is not just a classification—it is a boundary that defines the edge of our problem-solving universe. When we talk about P vs. NP, we are not merely asking about polynomial-time solvability; we are questioning the fundamental structure of mathematical truth, whether shortcuts exist within the inferential machinery of the universe, and whether intelligence—human or artificial—can ever transcend its own algorithmic nature.
But the brilliance of this work is not in its exposition of the standard computational landscape. It is in the way it seamlessly integrates statistical mechanics, phase transitions, and quantum complexity theory into a single, unified narrative. The relationship between entropy, information, and computational hardness is not an analogy—it is a physical reality. The deep connections between spin glasses, satisfiability problems, and error correction suggest that computation is embedded in nature at a far more fundamental level than we previously assumed.
Turing machines and cellular automata are not just abstract constructs; they model the very fabric of physical law. The halting problem is not simply an exercise in undecidability—it is a mirror reflecting the incompleteness of any finite system attempting to understand itself. The real bombshell of this book is that computational intractability is not a failure of mathematics—it is a defining feature of reality itself.
This is not just theory—it’s a shift in perspective. Once you understand the fundamental constraints of computation, you start to see them everywhere: in physics, in logic, in the limitations of knowledge itself. It’s not about whether a problem is solvable; it’s about whether it even fits within the space of what can be computed. And that distinction changes everything.
This book operates at the intersection of computer science, mathematics, and physics, dissecting computational complexity not as a mere theoretical curiosity but as an unavoidable constraint on knowledge itself. NP-completeness is not just a classification—it is a boundary that defines the edge of our problem-solving universe. When we talk about P vs. NP, we are not merely asking about polynomial-time solvability; we are questioning the fundamental structure of mathematical truth, whether shortcuts exist within the inferential machinery of the universe, and whether intelligence—human or artificial—can ever transcend its own algorithmic nature.
But the brilliance of this work is not in its exposition of the standard computational landscape. It is in the way it seamlessly integrates statistical mechanics, phase transitions, and quantum complexity theory into a single, unified narrative. The relationship between entropy, information, and computational hardness is not an analogy—it is a physical reality. The deep connections between spin glasses, satisfiability problems, and error correction suggest that computation is embedded in nature at a far more fundamental level than we previously assumed.
Turing machines and cellular automata are not just abstract constructs; they model the very fabric of physical law. The halting problem is not simply an exercise in undecidability—it is a mirror reflecting the incompleteness of any finite system attempting to understand itself. The real bombshell of this book is that computational intractability is not a failure of mathematics—it is a defining feature of reality itself.
This is not just theory—it’s a shift in perspective. Once you understand the fundamental constraints of computation, you start to see them everywhere: in physics, in logic, in the limitations of knowledge itself. It’s not about whether a problem is solvable; it’s about whether it even fits within the space of what can be computed. And that distinction changes everything.
August 14, 2021
Very thorough
This is a textbook so expect to take some time on it. Technically it is about computational complexity so the title could be seen as a bit misleading. The first half is excellent. Superb coverage of complexity, P, NP and NP-Completeness. And yes some info on theories of computation itself. I found the second half a bit harder to follow. Randomness in many of its aspects. Maybe that’s just me or maybe it’s not as clearly written. Nah ... it’s them. The final chapter on quantum computing was a bit rushed. You’re not going to learn much from it unless you already know it. Though the discussion on quantum mechanics itself is pretty good and deftly avoids all of the standard nonsense.
The relationship between deterministic, probabilistic and quantum computing is a very hot issue these days. This book looks at this and makes many interesting points. The authors dismiss out of hand any kind of transfinite/continuous computing and probably with very good reasons. Maybe. Maybe not.
There is very little discussion on non-computability and unsolvability. I guess if the focus is on how intrinsically hard it is to solve problems then infinitely hard is about all that can be said in these cases.
This is a textbook so expect to take some time on it. Technically it is about computational complexity so the title could be seen as a bit misleading. The first half is excellent. Superb coverage of complexity, P, NP and NP-Completeness. And yes some info on theories of computation itself. I found the second half a bit harder to follow. Randomness in many of its aspects. Maybe that’s just me or maybe it’s not as clearly written. Nah ... it’s them. The final chapter on quantum computing was a bit rushed. You’re not going to learn much from it unless you already know it. Though the discussion on quantum mechanics itself is pretty good and deftly avoids all of the standard nonsense.
The relationship between deterministic, probabilistic and quantum computing is a very hot issue these days. This book looks at this and makes many interesting points. The authors dismiss out of hand any kind of transfinite/continuous computing and probably with very good reasons. Maybe. Maybe not.
There is very little discussion on non-computability and unsolvability. I guess if the focus is on how intrinsically hard it is to solve problems then infinitely hard is about all that can be said in these cases.
April 10, 2023
A bit of a challenge but very fun and probably the best intro to graph theory I could ask for. Most of the exercises after some of the early stuff on NP Completeness in chapter 5 are out of reach for me but I think it was really informative . I think it’s explanation of the Halting Problem was better than the one in computability and it’s logic (which is considered a more canonical text).
August 26, 2023
If you are studying computer science, it is a must read.
Displaying 1 - 8 of 8 reviews