دانلود کتاب Theory of Computational Complexity

“Complexity theory studies the inherent difficulties of solving algorithmic problems by digital computers. This comprehensive work discusses the major topics in complexity theory, including fundamental topics as well as recent breakthroughs not previously available in book form.”–BOOK JACKET. Part I Uniform Complexity 1 — 1 Models of Computation and Complexity Classes 3 — 1.1 Strings, Coding, and Boolean Functions 3 — 1.2 Deterministic Turing Machines 7 — 1.3 Nondeterministic Turing Machines 14 — 1.4 Complexity Classes 18 — 1.5 Universal Turing Machine 24 — 1.6 Diagonalization 27 — 1.7 Simulation 31 — 2 NP-Completeness 43 — 2.1 NP 43 — 2.2 Cook’s Theorem 47 — 2.3 More NP-Complete Problems 51 — 2.4 Polynomial-Time Turing Reducibility 58 — 2.5 NP-Complete Optimization Problems 64 — 3 Polynomial-Time Hierarchy and Polynomial Space 77 — 3.1 Nondeterministic Oracle Turing Machines 77 — 3.2 Polynomial-Time Hierarchy 79 — 3.3 Complete Problems in PH 84 — 3.4 Alternating Turing Machines 90 — 3.5 PSPACE-Complete Problems 95 — 3.6 EXP-Complete Problems 102 — 4 Structure of NP 113 — 4.1 Incomplete Problems in NP 113 — 4.2 One-Way Functions and Cryptography 119 — 4.3 Relativization 125 — 4.4 Unrelativizable Proof Techniques 127 — 4.5 Independence Results 127 — 4.6 Positive Relativization 129 — 4.7 Random Oracles 131 — 4.8 Structure of Relativized NP 135 — Part II Nonuniform Complexity 145 — 5 Decision Trees 147 — 5.1 Graphs and Decision Trees 147 — 5.3 Algebraic Criterion 157 — 5.4 Monotone Graph Properties 161 — 5.5 Topological Criterion 163 — 5.6 Applications of the Fixed Point Theorems 170 — 5.7 Applications of Permutation Groups 173 — 5.8 Randomized Decision Trees 176 — 5.9 Branching Programs 181 — 6 Circuit Complexity 195 — 6.1 Boolean Circuits 195 — 6.2 Polynomial-Size Circuits 199 — 6.3 Monotone Circuits 205 — 6.4 Circuits with Modulo Gates 213 — 6.5 NC 216 — 6.6 Parity Function 221 — 6.7 P-Completeness 229 — 6.8 Random Circuits and RNC 234 — 7 Polynomial-Time Isomorphism 245 — 7.1 Polynomial-Time Isomorphism 245 — 7.2 Paddability 249 — 7.3 Density of NP-Complete Sets 254 — 7.4 Density of EXP-Complete Sets 262 — 7.5 One-Way Functions and Isomorphism in EXP 266 — 7.6 Density of P-Complete Sets 276 — Part III Probabilistic Complexity 285 — 8 Probabilistic Machines and Complexity Classes 287 — 8.1 Randomized Algorithms 287 — 8.2 Probabilistic Turing Machines 292 — 8.3 Time Complexity of Probabilistic Turing Machines 295 — 8.4 Probabilistic Machines with Bounded Errors 298 — 8.5 BPP and P 301 — 8.6 BPP and NP 304 — 8.7 BPP and the Polynomial-Time Hierarchy 306 — 8.8 Relativized Probabilistic Complexity Classes 310 — 9 Complexity of Counting 321 — 9.1 Counting Class #P 322 — 9.2 #P-Complete Problems 325 — 9.3 [plus sign in circle]P and the Polynomial-Time Hierarchy 334 — 9.4 #P and the Polynomial-Time Hierarchy 340 — 9.5 Circuit Complexity and Relativized [plus sign in circle]P and #P 342 — 9.6 Relativized Polynomial-Time Hierarchy 346 — 10 Interactive Proof Systems 353 — 10.2 Arthur-Merlin Proof Systems 361 — 10.3 AM Hierarchy Versus Polynomial-Time Hierarchy 365 — 10.4 IP Versus AM 372 — 10.5 IP Versus PSPACE 382 — 11 Probabilistically Checkable Proofs and NP-Hard Optimization Problems 393 — 11.1 Probabilistically Checkable Proofs 393 — 11.2 PCP Characterization of Nondeterministic Exponential Time 396 — 11.2.1 Proof 397 — 11.2.2 Multilinearity Test System 403 — 11.2.3 Sum Check System 408 — 11.3 PCP Characterization of NP 410 — 11.3.1 Proof System for NP Using O(log n) Random Bits 412 — 11.3.2 Low-Degree Test System 416 — 11.3.3 Composition of Two PCP Systems 419 — 11.3.4 Proof System Reading a Constant Number of Oracle Bits 424 — 11.4 Probabilistic Checking and Nonapproximability 430 — 11.5 More NP-Hard Approximation Problems 434