计算复杂性是现代数学中最美的领域之一，它与从物理学到生物学的其他科学也息息相关。但这种美往往被不必要的形式主义所掩盖，而交互式证明、密码学和量子计算等令人兴奋的最新成果常常被认为过于“先进”，无法向普通学生展现。这本书的目的是通过以一种清晰而愉悦的方式解释理论计算机科学的深刻思想来予以弥合。书中包括很多有趣且深刻的主题：Pvs。NP问题；迷宫和棋牌游戏的复杂性；优化和估计；随机化算法、交互式证明和伪随机性；马尔可夫链和相变；以及量子计算等。

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