Moore Cristopher, Mertens Stephan. The Nature of Computation

Oxford University Press, 2011. — 985 p. — ISBN: 978-0199233212.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.Crossing Bridges
Intractable Itineraries
Playing Chess With God
What Lies AheadThe Basics
Problems and Solutions
Time, Space, and Scaling
Intrinsic Complexity
The Importance of Being Polynomial
Tractability and Mathematical InsightInsights and Algorithms
Recursion
Divide and Conquer
Dynamic Programming
Getting There From Here
When Greed is Good
Finding a Better Flow
Flows, Cuts, and Duality
Transformations and ReductionsNeedles in a Haystack: the Class NP
Needles and Haystacks
A Tour of NP
Search, Existence, and Nondeterminism
Knots and PrimesWho is the Hardest One of All? NP-Completeness
When One Problem Captures Them All
Circuits and Formulas
Designing Reductions
Completeness as a Surprise
The Boundary Between Easy and Hard
Finally, Hamiltonian PathThe Deep Question: P vs. NP
What if P-=NP?
Upper Bounds are Easy, Lower Bounds Are Hard
Diagonalization and the Time Hierarchy
Possible Worlds
Natural Proofs
Problems in the Gap
Nonconstructive Proofs
The Road AheadThe Grand Unified Theory of Computation
Babbage's Vision and Hilbert's Dream
Universality and Undecidability
Building Blocks: Recursive Functions
Form is Function: the 2.-Calculus
Turing's Applied Philosophy
Computation EverywhereMemory, Paths, and Garnes
Welcome to the State Space
Show Me The Way
L and NL-Completeness
Middle-First Search and Nondeterministic Space
You Can't Get There From Here
PSPACE, Garnes, and Quantified SAT
Garnes People Play
Symmetric SpaceOptimization and Approximation
Three Flavors of Optimization
Approximations
Inapproximability
Jewels and Facets: Linear Programming
Through the Looking-Glass: Duality
Solving by Balloon: Interior Point Methods
Hunting with Eggshells
Algorithmic Cubism
Trees, Tours, and Polytopes
Solving Hard Problems in PracticeRandomized Algorithms
Foiling the Adversary
The Smallest Cut
The Satisfied Drunkard: Wa1kSAT
Solving in Heaven, Projecting to Earth
Garnes Against the Adversary
Fingerprints, Hash Functions, and Uniqueness
The Roots of Identity
Primality
Randomized Complexity ClassesInteraction and Pseudorandomness
The Tale of Arthur and Merlin
The Fable of the Chess Master
Probabilistically Checkable Proofs
Pseudorandom Generators and DerandomizationRandom Walks and Rapid Mixing
A Random Walk in Physics
The Approach to Equilibrium
Equilibrium Indicators
Coupling
Coloring a Graph, Randomly
Burying Ancient History: Coupling from the Past
The Spectral Gap
Flows of Probability: Conductance
Expanders
Mixing in Time and SpaceCounting, Sampling, and Statistical Physics
Spanning Trees and the Determinant
Perfect Matchings and the Permanent
The Complexity of Counting
From Counting to Sampling, and Back
Random Matchings and Approximating the Permanent
Planar Graphs and Asymptotics an Lattices
Solving the Ising ModelWhen Formulas Freeze: Phase Transitions in Computation
Experiments and Conjectures
Random Graphs, Giant Components, and Cores
Equations of Motion: Algorithmic Lower Bounds
Magic Moments
The Easiest Hard Problem
Message Passing
Survey Propagation and the Geometry of Solutions
Frozen Variables and HardnessQuantum Computation
Particles, Waves, and Amplitudes
States and Operators
Spooky Action at a Distance
Algorithmic Interference
Cryptography and Shor's Algorithm
Graph Isomorphism and the Hidden Subgroup Problem
Quantum Haystacks: Grover's Algorithm
Quantum Walks and ScatteringMathematical Tools
The Story of 0
Approximations and Inequalities
Chance and Necessity
Dice and Drunkards
Concentration Inequalities
Asymptotic Integrals
Groups, Rings, and Fields