目錄
Figure Credits
Preface
1 Prologue
1.1 CrossingBridges
1.2 IntractableItineraries
1.3 Playing ChessWith God
1.4 What LiesAhead
Problems
Notes
2 The Basics
2.1 Problems and Solutions
2.2 Time，Space，and Scaling
2.3 Intrinsic Complexity
2.4 The Importance ofBeingPolynomial
2.5 TractabilityandMathematicalInsight
Problems
Notes
3 Insights and Algorithms
3.1 Recursion
3.2 Divide and Conquer
3.3 DynamicProgramming
3.4 GettingThere FromHere
3.5 When Greedis Good
3.6 FindingaBetterFlow
3.7 Flows，Cuts，and Duality
3.8 Transformations andReductions
Problems
Notes
4 NeedlesInaHaystack：theClassNP
4.1 Needles andHaystacks
4.2 AT0ur 0fNP
4.3 Search。Existence，andNondeterminism
4.4 Knots and Primes
Problems
Notes
5 WhO is the Hardest One of All?NP-Completeness
5.1 Ⅵmen 0ne Problem CapturesThemAll
5.2 Circuits andFormulas
5.3 DesigningReductions
5.4 Completeness as aSurprise
5.5 The BoundaryBetween EasyandHard
5.6 Finally,Hamfltonian path
Problems
Notes
6 The Deep Question：P vs.NP
6.1 WhatifP=NP
6.2 UpperBounds are Easy,LowerBoundsAre Hard
6.3 Diagonalization andthe Time Hierarchy
6.4 PossibleWbrlds
6.5 NaturalProofs
6.6 Problemsinthe Gap
6.7 Nonconstructive PrOOfs
6.8 The RoadAhead
Problems
Notes
7 The Grand Unified Theory of Computation
7.1 Babbage~Vision and Hilbert's Dream
7.2 Universalityand Undecidabnit、
7.3 BuildingBlocks：Recursive Functions
7.4 Formis Function：the A—Calculus
7.5 Turing'sApplied Philosophy
7.6 ComputationEverywhere
Problems
Notes
8 Memory,Paths,and Games
8.1 Wlelcometothe State Space
8.2 ShowMe TheWay
8.3 LandNL.Completeness
8.4 Middle.First Search and Nondeterministic Space
8.5 Y0u Cant GetThereFromHere
8.6 PSPACE，Games，and Quantified SAT
8.7 Games People Play
8.8 Symmetric Space
Problems
Notes
9 Optimization and Approximation
9.1 Three Flavors ofOptimization
9.2 Approximations
9.3 Inapproximability
9.4 Jewels andFacets：LinearProgramming
9.5 Throughthe Looking-Glass：Duality
9.6 SolvingbyBalloon：InteriorPointMethods
9.7 Huntingwitll EggsheHs
9.8 A1gorithmic Cubism
9.9 Trees，Tours，andPolytopes
9.10 SolvingHard ProblemsinPractice
Problems
Notes
10 Randomized Algorithms
10.1 FoilingtheAdversary
10.2 111e SmallestCut
10.3 The Satisfied Drunkard：WalkSAT
10.4 Solvingin Heaven.Projectingto Earth
10.5 GamesAgainsttheAdversary
10.6 Fingerprints，HashFunctions，andUniqueness
10.7 The Roots ofIdentity
10.8 Primalit、
10.9 Randomized ComplexityClasses
Problems
Notes
11 Interacflon and Pseudorandomness
11.1 TheTale ofArthurandMerlin
11.2 The Fable ofthe Chess Master
11.3 ProbabilisticallyCheckable Proofs
11.4 Pseudorandom Generators and Derandomization
Problems
Nores
12 Random Walks and Rapid Mixing
12.1 A Random、^mkin Physics
12.2 The Approachto Equfl~rium
12.3 EquflibriumIndicators
12.4 Coupling
....
12.5 Coloring aGraph.Randomly
12.6 BuryingAncientHistory：CouplingfromthePast
12.7 The Spectral Gap
12.8 FlOWS ofProbabnity：Conductance
12.9 Expanders
12.10 MixinginTime andSpace
Problems
Notes
13 Counting,Sampling，and StatisflcM Physics
13.1 SpanningTrees andthe Determinant
13.2 PerfectMatchings andthe Permanent
13.3 The ComplexityofCounting
13.4 From Countingto Sampling.and Back
13.5 RandomMatchings andApproximatingthePermanent
13.6 P1anal：Graphs andAsymptotics onLattices
13.7 SolvingtheIsingModel
Problems
Notes
14 When Formulas Freeze：Phase Transitons in Computation
14.1 Experiments and Coniectures
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 SpookyAction 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 MathematicalTools
A.1 The Story Of 0
A.2 Approximations and Inequalities
A.3 Chance and Necessity
A.4 Dice and Drunkards
A5 C0ncentration Inequalities
A.6 Asymptotic Integrals
A.7 Groups，Rings，and Fields
Problems
References
Index
[