Theory of Computational Complexity (2^nd Ed.) Wiley Series in Discrete Mathematics and Optimization Series

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 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.

Preface ix

Notes on the Second Edition xv

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 25

1.6 Diagonalization 29

1.7 Simulation 33

Exercises 38

Historical Notes 43

2 NP-Completeness 45

2.1 Np 45

2.2 Cook’s Theorem 49

2.3 More NP-Complete Problems 54

2.4 Polynomial-Time Turing Reducibility 61

2.5 NP-Complete Optimization Problems 68

Exercises 76

Historical Notes 79

3 The Polynomial-Time Hierarchy and Polynomial Space 81

3.1 Nondeterministic Oracle Turing Machines 81

3.2 Polynomial-Time Hierarchy 83

3.3 Complete Problems in PH 88

3.4 Alternating Turing Machines 95

3.5 PSPACE-Complete Problems 100

3.6 EXP-Complete Problems 108

Exercises 114

Historical Notes 117

4 Structure of NP 119

4.1 Incomplete Problems in NP 119

4.2 One-Way Functions and Cryptography 122

4.3 Relativization 129

4.4 Unrelativizable Proof Techniques 131

4.5 Independence Results 131

4.6 Positive Relativization 132

4.7 Random Oracles 135

4.8 Structure of Relativized NP 140

Exercises 144

Historical Notes 147

Part II Nonuniform Complexity 149

5 Decision Trees 151

5.1 Graphs and Decision Trees 151

5.2 Examples 157

5.3 Algebraic Criterion 161

5.4 Monotone Graph Properties 166

5.5 Topological Criterion 168

5.6 Applications of the Fixed Point Theorems 175

5.7 Applications of Permutation Groups 179

5.8 Randomized Decision Trees 182

5.9 Branching Programs 187

Exercises 194

Historical Notes 198

6 Circuit Complexity 200

6.1 Boolean Circuits 200

6.2 Polynomial-Size Circuits 204

6.3 Monotone Circuits 210

6.4 Circuits with Modulo Gates 219

6.5 Nc 222

6.6 Parity Function 228

6.7 P-Completeness 235

6.8 Random Circuits and RNC 242

Exercises 246

Historical Notes 249

7 Polynomial-Time Isomorphism 252

7.1 Polynomial-Time Isomorphism 252

7.2 Paddability 256

7.3 Density of NP-Complete Sets 261

7.4 Density of EXP-Complete Sets 271

7.5 One-Way Functions and Isomorphism in EXP 275

7.6 Density of P-Complete Sets 285

Exercises 289

Historical Notes 292

Part III Probabilistic Complexity 295

8 Probabilistic Machines and Complexity Classes 297

8.1 Randomized Algorithms 297

8.2 Probabilistic Turing Machines 302

8.3 Time Complexity of Probabilistic Turing Machines 305

8.4 Probabilistic Machines with Bounded Errors 309

8.5 BPP and P 312

8.6 BPP and NP 315

8.7 BPP and the Polynomial-Time Hierarchy 318

8.8 Relativized Probabilistic Complexity Classes 321

Exercises 327

Historical Notes 330

9 Complexity of Counting 332

9.1 Counting Class #P 333

9.2 #P-Complete Problems 336

9.3 ⊕P and the Polynomial-Time Hierarchy 346

9.4 #P and the Polynomial-Time Hierarchy 352

9.5 Circuit Complexity and Relativized ⊕P and #P 354

9.6 Relativized Polynomial-Time Hierarchy 358

Exercises 361

Historical Notes 364

10 Interactive Proof Systems 366

10.1 Examples and Definitions 366

10.2 Arthur–Merlin Proof Systems 375

10.3 AM Hierarchy Versus Polynomial-Time Hierarchy 379

10.4 IP Versus AM 387

10.5 IP Versus PSPACE 396

Exercises 402

Historical Notes 406

11 Probabilistically Checkable Proofs and NP-Hard Optimization Problems 407

11.1 Probabilistically Checkable Proofs 407

11.2 PCP Characterization of NP 411

11.2.1 Expanders 414

11.2.2 Gap Amplification 418

11.2.3 Assignment Tester 428

11.3 Probabilistic Checking and Inapproximability 437

11.4 More NP-Hard Approximation Problems 440

Exercises 452

Historical Notes 455

References 458

Index 480

DING-ZHU DU, PhD, is Professor in the Department of Computer Science at the University of Texas at Dallas. He has published over 180 journal articles in his areas of research interest, which include design and analysis of approximation algorithms for combinatorial optimization problems and communication networks. Dr. Du is also the coauthor of Problem Solving in Automata, Languages, and Complexity, also published by Wiley.