Theory of Computational Complexity, 2nd EditionISBN: 9781118306086
512 pages
June 2014

Description
Praise for the First Edition
"...complete, uptodate 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 NPcompleteness 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
 Endofchapter 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 stateoftheart software and computational methods to conduct research.
Table of Contents
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 17
1.5 Universal Turing Machine 23
1.6 Diagonalization 27
1.7 Simulation 31
Exercises 35
Historical Notes 41
2 NPCompleteness 43
2.1 NP 43
2.2 Cook’s Theorem 47
2.3 More NPComplete Problems 51
2.4 PolynomialTime Turing Reducibility 58
2.5 NPComplete Optimization Problems 64
Exercises 71
Historical Notes 75
3 The PolynomialTime Hierarchy and Polynomial Space 77
3.1 Nondeterministic Oracle Turing Machines 77
3.2 PolynomialTime Hierarchy 79
3.3 Complete Problems in PH 84
3.4 Alternating Turing Machines 90
3.5 PSPACEComplete Problems 95
3.6 EXPComplete Problems 102
Exercises 108
Historical Notes 111
4 Structure of NP 113
4.1 Incomplete Problems in NP 113
4.2 OneWay Functions and Cryptography 116
4.3 Relativization 122
4.4 Unrelativizable Proof Techniques 124
4.5 Independence Results 125
4.6 Positive Relativization 126
4.7 Random Oracles 128
4.8 Structure of Relativized NP 132
Exercises 137
Historical Notes 140
Part II Nonuniform Complexity 141
5 Decision Trees 143
5.1 Graphs and Decision Trees 143
5.2 Examples 149
5.3 Algebraic Criterion 153
5.4 Monotone Graph Properties 157
5.5 Topological Criterion 159
5.6 Applications of the Fixed Point Theorems 166
5.7 Applications of Permutation Groups 169
5.8 Randomized Decision Trees 172
5.9 Branching Programs 177
Exercises 184
Historical Notes 188
6 Circuit Complexity 191
6.1 Boolean Circuits 191
6.2 PolynomialSize Circuits 195
6.3 Monotone Circuits 201
6.4 Circuits with Modulo Gates 208
6.5 NC 212
6.6 Parity Function 217
6.7 PCompleteness 224
6.8 Random Circuits and RNC 230
Exercises 234
Historical Notes 237
7 PolynomialTime Isomorphism 241
7.1 PolynomialTime Isomorphism 241
7.2 Paddability 245
7.3 Density of NPComplete Sets 250
7.4 Density of EXPComplete Sets 258
7.5 OneWay Functions and Isomorphism in EXP 262
7.6 Density of PComplete Sets 272
Exercises 275
Historical Notes 278
Part III Probabilistic Complexity 281
8 Probabilistic Machines and Complexity Classes 283
8.1 Randomized Algorithms 283
8.2 Probabilistic Turing Machines 288
8.3 Time Complexity of Probabilistic Turing Machines 291
8.4 Probabilistic Machines with Bounded Errors 294
8.5 BPP and P 297
8.6 BPP and NP 300
8.7 BPP and the PolynomialTime Hierarchy 302
8.8 Relativized Probabilistic Complexity Classes 306
Exercises 311
Historical Notes 314
9 Complexity of Counting 317
9.1 Counting Class #P 318
9.2 #PComplete Problems 321
9.3 ⊕P and the PolynomialTime Hierarchy 330
9.4 #P and the PolynomialTime Hierarchy 336
9.5 Circuit Complexity and Relativized ⊕P and #P 338
9.6 Relativized PolynomialTime Hierarchy 342
Exercises 344
Historical Notes 347
10 Interactive Proof Systems 349
10.1 Examples and Definitions 349
10.2 ArthurMerlin Proof Systems 357
10.3 AM Hierarchy Versus PolynomialTime Hierarchy 361
10.4 IP Versus AM 368
10.5 IP Versus PSPACE 378
Exercises 383
Historical Notes 386
11 Probabilistically Checkable Proofs and NPHard Optimization Problems 389
11.1 Probabilistically Checkable Proofs 389
11.2 PCP Characterization of NP 392
11.2.1 Expanders 396
11.2.2 Gap Amplification 399
11.2.3 Assignment Testers 410
11.4 Probabilistic Checking and Inapproximability 418
11.5 More NPHard Approximation Problems 421
Exercises 432
Historical Notes 435
Bibliography 439
Index 461
Author Information
DINGZHU 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.
KERI KO, PhD, is Professor in the Department of Computer Science at National Chiao Tung University, Taiwan. He has published extensively in his areas of research interest, which include computational complexity theory and its applications to numerical computation. Dr. Ko is also the coauthor of Problem Solving in Automata, Languages, and Complexity, also published by Wiley.