The nature of computation

Incluye índice y bibliografía.

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