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