The Nature of Computation

2011/08/11 by Cristopher Moore, Stephan Mertens · 8 citations
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Advanced Graph Theory Research

paper · doi:10.1093/acprof:oso/9780199233212.001.0001

openalex publication_date 2011/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

Abstract

Abstract 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. However, this beauty is often buried underneath layers of unnecessary formalism, and exciting recent results such as interactive proofs, phase transitions, and quantum computing are usually considered too advanced for the typical student. This book bridges these gaps by explaining the deep ideas of theoretical computer science in a clear fashion, making them accessible to non-computer scientists and to computer scientists who finally want to appreciate their field from a new point of view. It starts with a lucid explanation of the P vs. NP problem, explaining why it is so fundamental, and so hard to resolve. It then leads the reader through the complexity of mazes and games; optimisation in theory and practice; randomised algorithms, interactive proofs, and pseudorandomness; Markov chains and phase transitions; and the outer reaches of quantum computing. At every turn, it uses a minimum of formalism, providing explanations that are both deep and accessible.

Citations

• Über die Bausteine der mathematischen Logik
• Sur le problème des courbes gauches en Topologie
• Typical random 3-SAT formulae and the satisfiability threshold
• Local statistics for random domino tilings of the Aztec diamond
• Computational Complexity
• Representation Theory
• Every planar map is four colorable. Part II: Reducibility
• Eigenvalues and expanders
• Every planar map is four colorable. Part I: Discharging
• Parallel Quantum Computation and Quantum Codes
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Spatial search and the Dirac equation
• When action is not least
• Ueber die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren
• Quantum Computation and Decision Trees
• Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
• The chemical basis of morphogenesis
• Limit on the Speed of Quantum Computation in Determining Parity
• Matching is as easy as matrix inversion
• Simulating Ising spin glasses on a quantum computer
• The Factorization of Linear Graphs
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?
• Speedup via quantum sampling
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Two-Bit Gates are Universal for Quantum Computation
• A Mathematical Theory of Communication
• Hard Tiling Problems with Simple Tiles
• Exponential algorithmic speedup by a quantum walk
• Algebrization
• Wave–particle duality of C60 molecules
• The undecidability of the domino problem
• Konstruktion nichtrekursiver Funktionen
• Shortest Connection Networks And Some Generalizations
• Expander graphs and their applications
• The first example of a recursive function which is not primitive recursive
• Universality in the level statistics of disordered systems
• P = BPP if E requires exponential circuits
• Mathematical Methods of Organizing and Planning Production
• Exact sampling with coupled Markov chains and applications to statistical mechanics
• The complexity of theorem-proving procedures
• The Relative Complexity of NP Search Problems
• Communication Capacity of Quantum Computation
• Nondeterministic Space is Closed under Complementation
• Recursive functions of symbolic expressions and their computation by machine, Part I
• Recursion and double recursion
• Classes of recursively enumerable sets and their decision problems
• A single quantum cannot be cloned
• On the Structure of Polynomial Time Reducibility
• On the impossibility of a quantum sieve algorithm for graph isomorphism
• Equation of State Calculations by Fast Computing Machines
• NP is as easy as detecting unique solutions
• Computational Complexity of Probabilistic Turing Machines
• Parity, circuits, and the polynomial-time hierarchy
• The Complexity of Computing Steiner Minimal Trees
• An algorithm for the machine calculation of complex Fourier series
• Relative to a Random OracleA, \bf P^A ≠ \bf NP^A ≠ co-\bf NP^A with Probability 1
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Dimer problem in statistical mechanics-an exact result
• Equilibrium points in n -person games
• Algorithms for Scheduling Independent Tasks
• Gauss and the history of the fast Fourier transform
• Über eine Eigenschaft der ebenen Komplexe
• The complexity of loop programs
• Shuffling Cards and Stopping Times
• Crystal Statistics. I. A Two-Dimensional Model with an Order-Disorder Transition
• Zum Hilbertschen Aufbau der reellen Zahlen
• Zur Theorie der Gesellschaftsspiele
• Algebraic methods for interactive proof systems
• Schnelle Multiplikation großer Zahlen
• A fast quantum mechanical algorithm for database search
• Nonlinear Quantum Mechanics Implies Polynomial-Time Solution forNP-Complete and #PProblems
• Interactive proofs and the hardness of approximating cliques
• The Othello game on an n × n board is PSPACE-complete
• A complete anytime algorithm for number partitioning
• Computing a perfect strategy for n × n chess requires time exponential in n
• The Spontaneous Magnetization of a Two-Dimensional Ising Model
• Gobang ist PSPACE-vollst�ndig
• Using dual approximation algorithms for scheduling problems theoretical and practical results
• Elementary gates for quantum computation
• How easy is local search?
• Bounds on Multiprocessing Timing Anomalies
• The FFT: an algorithm the whole family can use
• Electron Diffraction at Multiple Slits
• Quantum Algorithms Revisited
• The Complexity of Enumeration and Reliability Problems
• Random Subcubes as a Toy Model for Constraint Satisfaction Problems
• FLASH?A superluminal communicator based upon a new kind of quantum measurement
• Three models for the description of language
• Decoherence, einselection, and the quantum origins of the classical
• On Computable Numbers, with an Application to the Entscheidungsproblem
• A probabilistic algorithm for k-SAT and constraint satisfaction problems
• From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups
• How to share a secret
• The knowledge complexity of interactive proof-systems
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Trailing the Dovetail Shuffle to its Lair
• New directions in cryptography
• Approximation algorithms for NP-complete problems on planar graphs
• A proof of the Kepler conjecture
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• PRIMES is in P
• Quantum circuit complexity
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Algorithms for quantum computation: discrete logarithms and factoring
• A note on two problems in connexion with graphs
• An inherently iterative computation of ackermann's function
• An Unsolvable Problem of Elementary Number Theory
• A Set of Postulates for the Foundation of Logic
• Numerical recipes: the art of scientific computing
• Universality in Elementary Cellular Automata
• Natural Proofs
• Semidefinite Programming
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Hamiltonian oracles
• Maximal Flow Through a Network
• The NP-completeness column: An ongoing guide
• A method for obtaining digital signatures and public-key cryptosystems
• Paths, Trees, and Flowers
• Irreversibility and Heat Generation in the Computing Process
• Some improvements in practical Fourier analysis and their application to x-ray scattering from liquids
• Alternation
• Conservative logic
• Non-deterministic exponential time has two-prover interactive protocols
• Quantum Digital Signatures

Cited by

• Computable functions as Reeb flows
• Does greed help a forager survive?
• Renormalization and scaling in quantum walks
• Branch-and-Bound Tensor Networks for Exact Ground-State Characterization
• Sustaining Moore's Law Through Inexactness
• Glassy Phase of Optimal Quantum Control
• Min (A)cyclic Feedback Vertex Sets and Min Ones Monotone 3-SAT
• Harry R. Lewis [wikipedia]

Related

• Limits on Efficient Computation in the Physical World
• Computational Complexity
• Applying computational complexity to the emergence of classicality
• One Complexity Theorist's View of Quantum Computing
• Where do hard problems really exist?