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

Computational complexity theory has been a central area of theoretical computer science since its early development in the mid-1960s. The subsequent rapid development in the next three decades has not only established it as a rich exciting theory, but also shown strong influence on many other related areas in computer science, mathematics, and operations research. We may roughly divide its development into three periods. The works from the mid-1960s to the early 1970s paved a solid foundation for the theory of feasible computation. The Turing-machine-based complexity theory and the axiomatic complexity theory established computational complexity as an independent mathematics discipline. The identification of polynomial-time computability with feasible com-put ability and the discovery of the NP-complete problems consolidated the P versus NP question as the central issue of the complexity theory.
From the early 1970s to the mid-1980s, research in computational complexity expanded at an exponential rate both in depth and in breadth. Various new computational models were proposed as alternatives to the traditional deterministic models. Finer complexity hierarchies and complexity classes were identified from these new models and more accu-rate classifications have been obtained for the complexity of practical algorithmic problems. Parallel computational models, such as alternating Turing machines and parallel random access machines, together with the NC hierarchy, provide a tool for the classification of the complexity of feasible problems. Probabilistic Turing machines area model for the complexity theory of distribution-independent randomized algo-rithms. Interactive proof systems, an extension of probabilistic Turing machines, and communication complexity study the complexity aspect of distributed or interactive computing. The study of one-way func-tions led to a breakthrough in cryptography. A theory of average-case completeness, based on the notion of distribution-faithful reductions, aims at establishing the foundation for the distribution-dependent average-case complexity. Boolean and threshold circuits are models for nonuniform complexity in which algebraic and topological methods have found interesting applications. Oracle Turing machines are the model for the theory of relativization in which combinatorial techniques meet recursion-theoretic techniques. Program-size complexity (or the Kolmogorov complexity) formalizes the notion of descriptive complexity and has strong connections with computational complexity. Although the central questions remain open, these developments demonstrate that computational complexity is a rich discipline with both a deep mathematical theory and a diverse area of applications.
Beginning in the mid-1980s, we have seen a number of deep surpris-ing results using diverse sophisticated proof techniques. In addition, seemingly independent subareas have found interesting connections. The exponential lower bounds for monotone circuits and constant-depth circuits have been found using probabilistic and algebraic methods. The connection between constant-depth circuits and relativization led to the relativized separation of the polynomial-time hierarchy. The technique of nondeterministic iterative counting has been used to collapse the nonde-terministic space hierarchy. The study of probabilistic reductions gave us the surprising result about the power of the counting class #P versus the polynomial-time hierarchy. Arithmetization of Boolean computation in interactive proof systems collapses the class of polynomial space to the class of sets with interactive proof systems. Further development of this research, together with techniques of coding theory, have led to strong negative results in combinatorial approximation.
As outlined above, complexity theory has grown fast both in breadth and in depth. With so many new computational models, new proof techniques, and applications in different areas, it is simply not possible to cover all important topics of the theory in a single book. The goal of this book is, therefore, not to provide a comprehensive treatment of complexity theory. Instead, we only select some of the fundamental areas that we believe represent the most important recent advances in complexity theory, in particular, on the P versus NP problem and present the complete treatment of these subjects. The presentation follows the approach of traditional mathematics textbooks. With a small number of exceptions, all theorems a represented with rigorous mathematical proofs.
We divide the subjects of this book into three parts, each repre-senting a different approach to computational complexity. In Part I, we develop the theory of uniform computational complexity, which is based on the worst-case complexity measures on traditional models of Turing machines, both deterministic ones and nondeterministic ones. The central issue here is the P versus NP question, and we apply the notions of reducibility and completeness to develop a complexity hierarchy. We first develop the notion of time and space complexity and complexity classes, in Chapter 1. Two basic proof techniques, simulation and diagonalization, including Immerman and Szelepc-senyi's iterative counting technique, a represented. The knowledge of recursion theory is useful here but is not required. Chapter 2 presents the notion of NP-completeness, including Cook's theorem and a few well-known NP-complete problems. The relations between decision problems versus search problems are carefully discussed through the notion of polynomial-time Turing reducibility. Chapter 3 extends the theory of NP-completeness to the polynomial-time hierarchy and polynomial space. In addition to complete problems for these com-plexity classes,we also present the natural characterizations of these complexity classes by alternating Turing machines and alternating quantifiers. In Chapter 4, the structure of the class NP is analyzed in several different views. We present both the abstract proof that there exist problems in NP that are neither NP-completenor in P assuming NP does not collapse to P, and some natural problems as the candidates of such problems,as well as their applications in public-key cryptography. The controversial theory of relativization and their interpretations are also introduced and discussed in this chapter.
In Part II, we study the theory of nonuniform computational complex-ity, including the computational models of decision trees and Boolean circuits, and the notion of sparse sets. The nonuniform computational models grew out of our inability to solve the major open questions in the uniform complexity theory. It is hoped that the simpler structure of these nonuniform models will allow better lower bound results. Although the efforts sofa rare not strong enough to settle the major open questions in the area of uniform complexity theory, a number of nontrivial lower bound results have been obtained through new proof techniques. The emphasis of this part is therefore not on the subjects themselves but on the proof techniques. In Chapter 5, we present both the algebraic and the topological techniques to prove the lower bounds for decision trees of Boolean functions, particularly Boolean functions representing monotone graph properties. In Chapter 6, we present two exponential lower bound results on circuits using the approximation circuit technique and the probabilistic method. The notion of sparse sets links the study of nonuniform complexity with uniform complexity theory. This interesting interconnection between uniform and nonuniform complexity theory, such as the question of NC versus P, is also studied in Chapter 6. Then, we present, in Chapter 7, the works on the Hartmanis-Berman conjec-ture about the polynomial-time isomorphism of NP-complete problems, which provide further insight into the structure of the complexity class NP.
Part III is about the theory of probabilistic complexity, which studies the complexity issues related to randomized computation. Randomiza-tion in algorithms started in the late 1970s and has become increasingly popular. The computational model for randomized algorithms, the prob-abilistic Turing machine, and the corresponding probabilistic complexity classes are introduced in Chapter 8. The notion of probabilistic quan-tifiers is used to provide characterizations of these complexity classes, and their relations with deterministic and nondeterministic complexity classes are discussed. The counting problems and the complexity class #P maybe viewed as an extension of probabilistic computation, and they are the main subjects of Chapter 9. Valiant's proof of #P-completeness of the permanent problem, as well as Toda's theorem that all problems in the polynomial-time hierarchy are reducible to problems in#P, are presented. The exponential lower bound of constant-depth circuits developed in Chapter 6hasan interesting application to the relativized separation of the complexity class #P from the polynomial-time hier-archy. This result is also presented in Chapter 9. Chapter 10 studies the notion of interactive proof systems, which is another extension of probabilistic computation. The collapse of the interactive proof systems hierarchy is presented, and the relations between the interactive proof systems and the Arthur-Merlin proof systems are discussed. Shamir's characterization of polynomial space by interactive proof systems is also presented as a prelude to the recent breakthrough on probabilistically checkable proofs. This celebrated result of Arora et al. , that probabilis-tically checkable proofs with a constant number of queries characterize precisely the class NP, is presented in Chapter 11. We also present, in this chapter, the application of this result to various combinatorial approximation problems.
Although we have tried to include, within this framework, as many sub-jects in complexity theory as possible, many interesting topics inevitably have to be omitted. Two of the most important topics that we are not able to include here are program-size complexity (or the Kolmogorov complexity) and average-case completeness. Program-size complexity is a central theory that would provide a unified view of the other nonuniform models of Part II. However, this topic has grown into an independent discipline in recent years and has become too big to be included in this book. Interested readers are referred to the comprehensive book of Li and Vitanyi (1997) . Average-case completeness provides a different view toward the notion of distribution-independent average-case complexity and would complement the works studied in Part III about distribution-independent probabilistic complexity. This theory, however, seems to be still in the early development stage. Much research is needed before we can better understand its proof techniques and its relation to the worst-case complexity theory, and we reluctantly omit i there. We refer interested readers to Wang (1997) for a thorough review of this topic. Exercises at the end of each chapter often include additional topics that are worth studying but are omitted in the main text owing to space limitations.
This book is grown out of authors’ lecture notes developed in the past 10 years at the University of Minnesota and the State University of New York at Stony Brook. We have taught from these notes in several different ways. For a one-semester graduate course in which the students have had limited exposure to theory, we typically cover most of Part I plus a couple of chapters from either Part II or Part III. For better prepared students, a course emphasizing the recent advances can be taught based mainly on either Part II or Part III. Seminars based on some advanced materials in Parts II and III, plus recent journal papers, have also been conducted for Ph. D. students.
We are grateful to all our colleagues and students who have made pre-cious suggestions, corrections, and criticism on the earlier drafts of this book. We are also grateful to the following institutions for their finan-cial support in preparing this book：the National Science Foundation of the United States, National Science Council of Taiwan, National Natural Science Foundation of China, National 973 Fundamental Research Pro-gram of China, City University of Hong Kong, and National Chiao Tung University of Taiwan.
DING-ZHU Du
KER-I Ko

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

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

中科院文献情报中心