The Nature of Computation: A Reader's Journal

These are notes captured while reading Cristopher Moore and Stephan Mertens’ The Nature of Computation. The text frames computational complexity as a property of physical systems, moving from the logic of P vs NP to the statistical mechanics of random SAT.

Log: Aug 2025 – Oct 2025

[2025-08-04] Computation is not about computers. It’s about the structure of problems. A problem has a shape. That shape dictates whether it yields to brute force or demands cleverness. The machine is irrelevant at first.

[2025-08-06] P versus NP lands on page one, not as a footnote but as the central crack in the universe. The question divides problems into those whose solutions can be checked easily and those whose solutions can be found easily. No one knows if the two sets are the same.

[2025-08-08] Hamiltonian path. Traveling salesman. These problems feel different but share a deep structure. The book wastes no time showing the isomorphism. Pattern recognition again. The problem’s costume changes. Its skeleton stays the same.

[2025-08-10] A Turing machine is a strip of tape and a head that reads, writes, shifts. That’s it. All computation reduces to this. The power is not in the hardware. It’s in the logic of state transitions. Minimal primitives, infinite reach.

[2025-08-12] Reduction. Take problem A, warp its inputs and outputs, and you have problem B. If B is hard, A is hard. The reduction is a lever. It transfers difficulty from one problem to another without solving either directly.

[2025-08-14] The book distinguishes decision problems from optimization problems. One asks yes or no. The other asks how much. But they intertwine. Solve the decision version and you often unlock the optimization. Structure the question right.

[2025-08-16] NP-completeness is a club. Thousands of problems belong. If you solve one efficiently, you solve them all. The unity beneath diversity is staggering. The world’s messiest problems share a single hidden order.

[2025-08-18] Cook’s theorem. SAT is the root. Every NP problem reduces to satisfiability. The Boolean formula sits at the base of the hardness tree. Find a fast SAT solver and the tree topples.

[2025-08-20] The book moves through graphs, circuits, and formulas without breaking stride. Each chapter is a new lens on the same landscape. A problem that looks geometric turns out to be combinatorial. A circuit problem becomes a graph problem. Fluidity of perspective.

[2025-08-22] Randomized algorithms appear. They flip coins and sometimes lie. But their lies are bounded. A Monte Carlo algorithm gambles and might be wrong. A Las Vegas algorithm gambles and might be slow. But both beat deterministic despair.

[2025-08-24] Primality testing. Once a hard problem. Now in P. The AKS algorithm proved it. Hardness is not permanent. A problem’s status can collapse overnight. The map is provisional.

[2025-08-26] Phase transitions. Random 3-SAT problems shift from easy to hard to easy as clause density rises. The hardest problems cluster at the threshold. The boundary between order and chaos is where computation sweats.

[2025-08-28] Approximation algorithms step in where exact solutions fear to tread. You give up perfection. You get a guarantee. A ρ-approximation promises you’re within a factor of optimal. Sometimes near enough is the smart play.

[2025-08-30] The gap between P and NP is not the only cliff. PSPACE, EXPTIME, the polynomial hierarchy. Problems stack upward in difficulty. The landscape has altitude. Most people only see the first peak.

[2025-09-02] Interactive proofs. A prover tries to convince a verifier. The verifier asks questions. The protocol reveals truth without revealing why. Zero-knowledge proofs hide the secret and still persuade. Proof as conversation.

[2025-09-04] Quantum computation enters. Qubits replace bits. Superposition and entanglement replace deterministic states. Shor’s algorithm factors integers in polynomial time. The hardness of factoring—assumed for decades—crumbles under quantum logic.

[2025-09-06] But quantum is not magic. BQP sits between P and NP. It breaks some cryptosystems but not all. The book draws the boundary with precision. Quantum expands the feasible. It does not make the impossible trivial.

[2025-09-08] The nature of computation is fundamentally about resources. Time. Space. Randomness. Interaction. Each resource is a dimension. A problem is a point in this multidimensional space. Complexity theory maps the terrain.

[2025-09-10] Circuit complexity. A problem’s hardness can be measured in gate count. Small depth circuits solve easy problems. Deep circuits handle harder ones. The silicon mirror of the polynomial hierarchy.

[2025-09-12] Information theory leaks into computation. Entropy. Kolmogorov complexity. A string’s compressibility is its randomness. An incompressible string has no shorter description. It is its own shortest program.

[2025-09-14] The book treats the physical limits of computation. Landauer’s principle. Reversible computing. Erasing a bit costs heat. Computation is physical. Bits are not abstract when they touch the world.

[2025-09-16] Optimization versus decision returns as a deeper theme. Many real-world problems demand the best answer, not just a yes. The book shows how to navigate when decision is easy but optimization is cruel.

[2025-09-18] Counting problems. #P complexity class. Not just finding a solution. Counting how many solutions exist. Harder than NP in a precise sense. The number of paths, the number of matchings. Enumeration as a separate frontier.

[2025-09-20] The polynomial hierarchy. Alternating quantifiers. There exists an x such that for all y there exists a z. Each layer adds a quantifier. Each layer may be strictly harder. The hierarchy may be infinite. No one knows.

[2025-09-22] The book’s elegance is its refusal to babble. Every proof is an artifact. The reduction from 3-SAT to Vertex Cover is a clean mechanism. Inputs become gadgets. Truth assignments become vertex selections. The logic crystallizes into graph structure.

[2025-09-24] Random walks. A simple process. Step randomly on a graph. The stationary distribution emerges. PageRank is a random walk. MCMC sampling is a random walk. Simplicity repeated yields global structure.

[2025-09-26] Cellular automata. Rule 110 is Turing complete. Complexity can emerge from the simplest neighborhood rule. The lesson repeats: simple primitives, local interactions, global surprise.

[2025-09-28] The book closes on the P versus NP question. Unsolved. A million-dollar prize waits. But the question’s value is not the answer. It’s the structure it has revealed. The chase has built a cathedral.

[2025-09-30] Computation is a lens, not a subject. It applies to physics, biology, economics. Any system that processes information is a computer. The natural world computes. The book’s title is literal.

[2025-10-02] The ultimate insight: hardness is not a wall. It is a resource. Cryptography relies on hardness. If P equals NP, modern encryption evaporates. The crack in the universe keeps secrets safe.

Synthesis: What The Nature of Computation Teaches

The Nature of Computation teaches that computation is a property of the universe, not a human invention. A river finding its path computes. A protein folding computes. A market settling on a price computes. The machine on your desk is a special case, not the definition.

The book maps the difficulty of problems as a geologist maps strata. P is the accessible surface. NP is the layer where solutions check easily but find stubbornly. Beyond lie PSPACE, EXPTIME, the polynomial hierarchy. Each stratum is a resource boundary. Time, space, randomness, interaction—these are the dimensions of the map.

Reduction is the fundamental tool. It says: this problem hides inside that problem. A fast algorithm for one topples the other. The web of reductions shows that thousands of seemingly unrelated problems share an identical core. Diversity collapses to unity.

Randomness, interaction, and quantum mechanics alter the landscape but do not flatten it. Each new resource expands what we can compute efficiently. Each has limits. The map grows more detailed, but the mountains remain.

The deepest lesson is that hardness has value. An easy problem offers no resistance and no security. A hard problem is a lock. Cryptography, digital signatures, secure communication—all rest on the assumption that certain problems resist fast solution. The crack in the universe between P and NP is not a flaw. It is the foundation of trust in a digital world.

Finally, the book teaches intellectual posture. Stand before a hard problem and ask not “Can I solve it?” but “What is its structure?” Classify it. Map its reductions. Understand its place in the hierarchy. The classification is the understanding. The problem may outlast you. That’s fine. The map is the achievement.