Figure Credits
Preface
1 Prologue
1.1 Crossing Bridges
1.2 Intractable Itineraries
1.3 Playing Chess With God
1.4 What Lies Ahead
Problems
Notes
2 The Basics
2.1 Problems and Solutions
2.2 Time, Space, and Scaling
2.3 Intrinsic Complexity
2.4 The Importance of Being Polynomial
2.5 Tractability and Mathematical Insight
Problems
Notes
3 Insights and Algorithms
3.1 Recursion
3.2 Divide and Conquer
3.3 Dynamic Programming
3.4 Getting There From Here
3.5 When Greed is Good
3.6 Finding a Better Flow
3.7 Flows, Cuts, and Duality
3.8 Transformations and Reductions
Problems
Notes
4 Needles in a Haystack: the Class NP
4.1 Needles and Haystacks
4.2 A Tour of NP
4.3 Search, Existence, and Nondeterminism
4.4 Knots and Primes
Problems
Notes
5 Who is the Hardest One of All? NP-Completeness
5.1 When One Problem Captures Them All
5.2 Circuits and Formulas
5.3 D esigning Reductions
5.4 Completeness as a Surprise
5.5 The Boundary Between Easy and Hard
5.6 Finally, Hamiltonian Path
Problems
Notes
6 The Deep Question: P vs. NP
6.1 What if P --=NP?
6.2 Upper Bounds are Easy, Lower Bounds Are Hard
6.3 Diagonalization and the Time Hierarchy
6.4 Possible Worlds
6.5 Natural Proofs
6.6 Problems in the Gap
6.7 Nonconstructive Proofs
6.8 The Road Ahead
Problems
Notes
7 The Grand Unified Theory of Computation
7.1 Babbage's Vision and Hilbert's Dream
7.2 Universality and Undecidability
7.3 Building Blocks: Recursive Functions
7.4 Form is Function: the 2.-Calculus
7.5 Turing's Applied Philosophy
7.6 Computation Everywhere
Problems
Notes
8 Memory, Paths, and Garnes
8.1 Welcome to the State Space
8.2 Show Me The Way
8.3 L and NL-Completeness
8.4 Middle-First Search and Nondeterministic Space
8.5 You Can't Get There From Here
8.6 PSPACE, Garnes, and Quantified SAT
8.7 Garnes People Play
8.8 Symmetric Space
Problems
Notes
9 Optimization and Approximation
9.1 Three Flavors of Optimization
9.2 Approximations
9.3 Inapproximability
9.4 Jewels and Facets: Linear Programming
9.5 Through the Looking-Glass: Duality
9.6 Solving by Balloon: Interior Point Methods
9.7 Hunting with Eggshells
9.8 Algorithmic Cubism
9.9 Trees, Tours, and Polytopes
9.10 Solving Hard Problems in Practice
Problems
Notes
10 Randomized Algorithms
10.1 Foiling the Adversary
10.2 The Smallest Cut
10.3 The Satisfied Drunkard: Wa1kSAT
10.4 Solving in Heaven, Projecting to Earth
10.5 Garnes Against the Adversary
10.6 Fingerprints, Hash Functions, and Uniqueness
10.7 The Roots of Identity
10.8 Primality
10.9 Randomized Complexity Classes
Problems
Notes
11 Interaction and Pseudorandomness
11.1 The Tale of Arthur and Merlin
11.2 The Fable of the Chess Master
11.3 Probabilistically Checkable Proofs
11.4 Pseudorandom Generators and Derandomization
Problems
Notes
12 Random Walks and Rapid Mixing
12.1 A Random Walk in Physics
12.2 The Approach to Equilibrium
12.3 Equilibrium Indicators
12.4 Coupling
12.5 Coloring a Graph, Randomly
12.6 Burying Ancient History: Coupling from the Past
12.7 The Spectral Gap
12.8 Flows of Probability: Conductance
12.9 Expanders
12.10 Mixing in Time and Space
Problems
Notes
13 Counting, Sampling, and Statistical Physics
13.1 Spanning Trees and the Determinant
13.2 Perfect Matchings and the Permanent
13.3 The Complexity of Counting
13.4 From Counting to Sampling, and Back
13.5 Random Matchings and Approximating the Permanent
13.6 Planar Graphs and Asymptotics an Lattices
13.7 Solving the Ising Model
Problems
Notes
14 When Formulas Freeze: Phase Transitions in Computation
14.1 Experiments and Conjectures
14.2 Random Graphs, Giant Components, and Cores
14.3 Equations of Motion: Algorithmic Lower Bounds
14.4 Magic Moments
14.5 The Easiest Hard Problem
14.6 Message Passing
14.7 Survey Propagation and the Geometry of Solutions
14.8 Frozen Variables and Hardness
Problems
Notes
15 Quantum Computation
15.1 Particles, Waves, and Amplitudes
15.2 States and Operators
15.3 Spooky Action at a Distance
15.4 Algorithmic Interference
15.5 Cryptography and Shor's Algorithm
15.6 Graph Isomorphism and the Hidden Subgroup Problem
15.7 Quantum Haystacks: Grover's Algorithm
15.8 Quantum Walks and Scattering
Problems
Notes
A Mathematical Tools
A.1 The Story of 0
A.2 Approximations and Inequalities
A.3 Chance and Necessity
A.4 Dice and Drunkards
A.5 Concentration Inequalities
A.6 Asymptotic Integrals
A.7 Groups, Rings, and Fields
Problems
References
Index
