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

Exercises 71

Historical Notes 75

**3 The 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

Exercises 108

Historical Notes 111

**4 Structure of ***NP* 113

4.1 Incomplete Problems in *NP* 113

4.2 One-Way 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 Polynomial-Size 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 *P*-Completeness 224

6.8 Random Circuits and *RNC* 230

Exercises 234

Historical Notes 237

**7 Polynomial-Time Isomorphism 241**

7.1 Polynomial-Time Isomorphism 241

7.2 Paddability 245

7.3 Density of *NP*-Complete Sets 250

7.4 Density of *EXP*-Complete Sets 258

7.5 One-Way Functions and Isomorphism in *EXP* 262

7.6 Density of P-Complete 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 Polynomial-Time 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 #*P*-Complete Problems 321

9.3 ⊕*P* and the Polynomial-Time Hierarchy 330

9.4 #*P* and the Polynomial-Time Hierarchy 336

9.5 Circuit Complexity and Relativized ⊕*P* and #*P* 338

9.6 Relativized Polynomial-Time Hierarchy 342

Exercises 344

Historical Notes 347

**10 Interactive Proof Systems 349**

10.1 Examples and Definitions 349

10.2 Arthur-Merlin Proof Systems 357

10.3 AM Hierarchy Versus Polynomial-Time Hierarchy 361

10.4 IP Versus *AM* 368

10.5 IP Versus *PSPACE* 378

Exercises 383

Historical Notes 386

**11 Probabilistically Checkable Proofs and NP-Hard 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 *NP*-Hard Approximation Problems 421

Exercises 432

Historical Notes 435

Bibliography 439

Index 461