Praise for the First Edition "e;... complete, up-to-date coverage of computational complexity theory...the book promises to become the standard reference on computational complexity."e; Zentralblatt MATH A thorough revision based on advances in the field of computational complexity and readers feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered. Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as: A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science Additional exercises at varying levels of difficulty to further test comprehension of the presented material End-of-chapter literature reviews that summarize each topic and offer additional sources for further study Theory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.

Praise for the First Edition"... complete, up-to-date coverage of computational complexity theory...the book promises to become the standard reference on computational complexity."Zentralblatt MATHA thorough revision based on advances in the field of computational complexity and readers' feedback, the Second Edition of Theory of Computational Complexity presents updates to the principles and applications essential to understanding modern computational complexity theory. The new edition continues to serve as a comprehensive resource on the use of software and computational approaches for solving algorithmic problems and the related difficulties that can be encountered.Maintaining extensive and detailed coverage, Theory of Computational Complexity, Second Edition, examines the theory and methods behind complexity theory, such as computational models, decision tree complexity, circuit complexity, and probabilistic complexity. The Second Edition also features recent developments on areas such as NP-completeness theory, as well as:* A new combinatorial proof of the PCP theorem based on the notion of expander graphs, a research area in the field of computer science* Additional exercises at varying levels of difficulty to further test comprehension of the presented material* End-of-chapter literature reviews that summarize each topic and offer additional sources for further studyTheory of Computational Complexity, Second Edition, is an excellent textbook for courses on computational theory and complexity at the graduate level. The book is also a useful reference for practitioners in the fields of computer science, engineering, and mathematics who utilize state-of-the-art software and computational methods to conduct research.

Preface ixNotes on the Second Edition xvPart I Uniform Complexity 11 Models of Computation and Complexity Classes 31.1 Strings, Coding, and Boolean Functions 31.2 Deterministic Turing Machines 71.3 Nondeterministic Turing Machines 141.4 Complexity Classes 171.5 Universal Turing Machine 231.6 Diagonalization 271.7 Simulation 31Exercises 35Historical Notes 412 NP-Completeness 432.1 NP 432.2 Cook's Theorem 472.3 More NP-Complete Problems 512.4 Polynomial-Time Turing Reducibility 582.5 NP-Complete Optimization Problems 64Exercises 71Historical Notes 753 The Polynomial-Time Hierarchy and Polynomial Space 773.1 Nondeterministic Oracle Turing Machines 773.2 Polynomial-Time Hierarchy 793.3 Complete Problems in PH 843.4 Alternating Turing Machines 903.5 PSPACE-Complete Problems 953.6 EXP-Complete Problems 102Exercises 108Historical Notes 1114 Structure of NP 1134.1 Incomplete Problems in NP 1134.2 One-Way Functions and Cryptography 1164.3 Relativization 1224.4 Unrelativizable Proof Techniques 1244.5 Independence Results 1254.6 Positive Relativization 1264.7 Random Oracles 1284.8 Structure of Relativized NP 132Exercises 137Historical Notes 140Part II Nonuniform Complexity 1415 Decision Trees 1435.1 Graphs and Decision Trees 1435.2 Examples 1495.3 Algebraic Criterion 1535.4 Monotone Graph Properties 1575.5 Topological Criterion 1595.6 Applications of the Fixed Point Theorems 1665.7 Applications of Permutation Groups 1695.8 Randomized Decision Trees 1725.9 Branching Programs 177Exercises 184Historical Notes 1886 Circuit Complexity 1916.1 Boolean Circuits 1916.2 Polynomial-Size Circuits 1956.3 Monotone Circuits 2016.4 Circuits with Modulo Gates 2086.5 NC 2126.6 Parity Function 2176.7 P-Completeness 2246.8 Random Circuits and RNC 230Exercises 234Historical Notes 2377 Polynomial-Time Isomorphism 2417.1 Polynomial-Time Isomorphism 2417.2 Paddability 2457.3 Density of NP-Complete Sets 2507.4 Density of EXP-Complete Sets 2587.5 One-Way Functions and Isomorphism in EXP 2627.6 Density of P-Complete Sets 272Exercises 275Historical Notes 278Part III Probabilistic Complexity 2818 Probabilistic Machines and Complexity Classes 2838.1 Randomized Algorithms 2838.2 Probabilistic Turing Machines 2888.3 Time Complexity of Probabilistic Turing Machines 2918.4 Probabilistic Machines with Bounded Errors 2948.5 BPP and P 2978.6 BPP and NP 3008.7 BPP and the Polynomial-Time Hierarchy 3028.8 Relativized Probabilistic Complexity Classes 306Exercises 311Historical Notes 3149 Complexity of Counting 3179.1 Counting Class #P 3189.2 #P-Complete Problems 3219.3 oplus P and the Polynomial-Time Hierarchy 3309.4 #P and the Polynomial-Time Hierarchy 3369.5 Circuit Complexity and Relativized oplus P and #P 3389.6 Relativized Polynomial-Time Hierarchy 342Exercises 344Historical Notes 34710 Interactive Proof Systems 34910.1 Examples and Definitions 34910.2 Arthur-Merlin Proof Systems 35710.3 AM Hierarchy Versus Polynomial-Time Hierarchy 36110.4 IP Versus AM 36810.5 IP Versus PSPACE 378Exercises 383Historical Notes 38611 Probabilistically Checkable Proofs and NP-Hard Optimization Problems 38911.1 Probabilistically Checkable Proofs 38911.2 PCP Characterization of NP 39211.2.1 Expanders 39611.2.2 Gap Amplification 39911.2.3 Assignment Testers 41011.4 Probabilistic Checking and Inapproximability 41811.5 More NP-Hard Approximation Problems 421Exercises 432Historical Notes 435Bibliography 439Index 461