Cover -- Title Page -- Contents -- Preface -- Notes on the Second Edition -- Part I Uniform Complexity -- Chapter 1 Models of Computation and Complexity Classes -- 1.1 Strings, Coding, and Boolean Functions -- 1.2 Deterministic Turing Machines -- 1.3 Nondeterministic Turing Machines -- 1.4 Complexity Classes -- 1.5 Universal Turing Machine -- 1.6 Diagonalization -- 1.7 Simulation -- Exercises -- Historical Notes -- Chapter 2 NP-Completeness -- 2.1 NP -- 2.2 Cook's Theorem -- 2.3 More NP-Complete Problems -- 2.4 Polynomial-Time Turing Reducibility -- 2.5 NP-Complete Optimization Problems -- Exercises -- Historical Notes -- Chapter 3 The Polynomial-Time Hierarchy and Polynomial Space -- 3.1 Nondeterministic Oracle Turing Machines -- 3.2 Polynomial-Time Hierarchy -- 3.3 Complete Problems in PH -- 3.4 Alternating Turing Machines -- 3.5 PSPACE-Complete Problems -- 3.6 EXP-Complete Problems -- Exercises -- Historical Notes -- Chapter 4 Structure of NP -- 4.1 Incomplete Problems in NP -- 4.2 One-Way Functions and Cryptography -- 4.3 Relativization -- 4.4 Unrelativizable Proof Techniques -- 4.5 Independence Results -- 4.6 Positive Relativization -- 4.7 Random Oracles -- 4.8 Structure of Relativized NP -- Exercises -- Historical Notes -- Part II Nonuniform Complexity -- Chapter 5 Decision Trees -- 5.1 Graphs and Decision Trees -- 5.2 Examples -- 5.3 Algebraic Criterion -- 5.4 Monotone Graph Properties -- 5.5 Topological Criterion -- 5.6 Applications of the Fixed Point Theorems -- 5.7 Applications of Permutation Groups -- 5.8 Randomized Decision Trees -- 5.9 Branching Programs -- Exercises -- Historical Notes -- Chapter 6 Circuit Complexity -- 6.1 Boolean Circuits -- 6.2 Polynomial-Size Circuits -- 6.3 Monotone Circuits -- 6.4 Circuits with Modulo Gates -- 6.5 NC -- 6.6 Parity Function -- 6.7 P-Completeness.

6.8 Random Circuits and RNC -- Exercises -- Historical Notes -- Chapter 7 Polynomial-Time Isomorphism -- 7.1 Polynomial-Time Isomorphism -- 7.2 Paddability -- 7.3 Density of NP-Complete Sets -- 7.4 Density of EXP-Complete Sets -- 7.5 One-Way Functions and Isomorphism in EXP -- 7.6 Density of P-Complete Sets -- Exercises -- Historical Notes -- Part III Probabilistic Complexity -- Chapter 8 Probabilistic Machines and Complexity Classes -- 8.1 Randomized Algorithms -- 8.2 Probabilistic Turing Machines -- 8.3 Time Complexity of Probabilistic Turing Machines -- 8.4 Probabilistic Machines with Bounded Errors -- 8.5 BPP and P -- 8.6 BPP and NP -- 8.7 BPP and the Polynomial-Time Hierarchy -- 8.8 Relativized Probabilistic Complexity Classes -- Exercises -- Historical Notes -- Chapter 9 Complexity of Counting -- 9.1 Counting Class #P -- 9.2 #P-Complete Problems -- 9.3 oplus P and the Polynomial-Time Hierarchy -- 9.4 #P and the Polynomial-Time Hierarchy -- 9.5 Circuit Complexity and Relativized oplus P and #P -- 9.6 Relativized Polynomial-Time Hierarchy -- Exercises -- Historical Notes -- Chapter 10 Interactive Proof Systems -- 10.1 Examples and Definitions -- 10.2 Arthur-Merlin Proof Systems -- 10.3 AM Hierarchy Versus Polynomial-Time Hierarchy -- 10.4 IP Versus AM -- 10.5 IP Versus PSPACE -- Exercises -- Historical Notes -- Chapter 11 Probabilistically Checkable Proofs and NP-Hard Optimization Problems -- 11.1 Probabilistically Checkable Proofs -- 11.2 PCP Characterization of NP -- 11.2.1 Expanders -- 11.2.2 Gap Amplification -- 11.2.3 Assignment Tester -- 11.3 Probabilistic Checking and Inapproximability -- 11.4 More NP-Hard Approximation Problems -- Exercises -- Historical Notes -- References -- Index -- Wiley Series in Discrete Mathematics and Optimization.