Contents
1 Introduction 1
1.1 What Is Complexity Theory 1
1.2 Didactic Background 5
1.3 Overview 6
1.4 Additional Literature 10
2 Algorithmic Problems & Their Complexity 11
2.1 What Are Algorithmic Problems 11
2.2 Some Important Algorithmic Problems 13
2.3 Measuring Computation Time 18
2 4 The Complexity of Algorithmic Problems 22
3 Fundamental Complexity Classes 25
3.1 The Special Role of Polynomial Computation Time 25
3.2 Ra ndomized Algorithms 27
3.3 The Fundamental Complexity Classes for Algorithmic Problems 30
3.4 The Fundamental Complexity Classes for Decision Problems 35
3.5 Nondeterminism as a Special Case of Ra ndomization 39
4 Reductions - AIgorithmic Relationships Between Problems 43
4.1 When Are Two Problems AIgorithmically Similar 43
4.2 Reductions Between Various Variants of a Problem 46
4.3 Reductions Between Rβlated Problems 49
4.4 Rβductions Between Unrelated Problems 53
4.5 The Special Role of Polynomial Reductions 60
5 The Theory of NP-Completeness 63
5.1 Fundamental Considerations 63
5.2 Problems in NP 67
5 3 Alternative Characteriz ations of NP 69
5 4 Cook's Theorem 70
6 NP-complete and NP-equivalent Problems 77
6.1 Fundamental Considerations 77
6.2τ'raveling Salesperson Problems 77
6.3 Knapsack Problems 78
6.4 Partitioning and Scheduling Problems 80
6.5 Clique Problems 81
6.6 Team Building Problems 83
6.7 Championship Problems 85
7 The Complexity Analysis of Problems 89
7.1 The Dividing Line Between Easy and Hard 89
7.2 Pseudo-polynomial Algorithms and Strong NP-completeness 93
7.3 An Overview of the NP-completeness Proofs Considered 96
8 The Complexity of Approximation Problems – Classical Results 99
8.1 Complexity Classes 99
8.2 Approximation Algorithms 103
8.3 The Gap Technique 106
8.4 Approximation-Preserving Rβductions 109
8.5 Complete Approximation Problems 112
9 The Complexity of Black Box Problems 115
9.1 Black Box Optimization 115
9.2 Yao's Minimax Principle 118
9.3 Lower Bounds for Black Box Complexity 120
10 Additional Complexity Classes 127
10.1 Fundamental Considerations 127
10.2 Complexity Classes Within NP and co-NP 128
10.3 Oracle Classes 130
10.4 The Polynomial Hierarchy 132
10.5 BPP， NP， and the Polynomial Hierarchy 138
11 Interactive Proofs 145
11.1 Fundamental Considerations 145
11.2 Interactive Proof Systems 147
11.3 Rβgarding the Complexity of Graph Isomorphism Problems 148
11.4 ZerφKnowledge Proofs 155
12 The PCP Theorem and the Complexity of Approximation
Problems 161
12.1 Randomized Verification of Proofs 161
12.2 The PCP Theorem 164
12.3 The PCP Theorem and Inapproximability Rβsults 173
12.4 The PCP Theorem and APX-Completeness 177
13 Further Topics From Classical Complexity Theory 185
13.1 Overview 185
13.2 SpacφBounded Complexity Classes 186
13.3 PSPACE-complete Problems 188
13.4 Nondeterminism and Determinism in the Context of Bounded Space 191
13.5 Nondeterminism and Complementation with Precise Space Bounds 193
13.6 Complexity Classes Within P 195
13.7 The Complexity of Counting Problems 198
14 The Complexity of Non-uniform Problems 201
14.1 Fundamental Considerations 201
14.2 The Simulation of Turing Machines By Circuits 204
14.3 The Simulation of Circuits by Non-uniform Turing Machines 206
14.4 Branching Programs and Space Bounds 209
14.5 Polynomial Circuits for Problems in BPP 211
14.6 Complexity Classes for Computation with Help 212
14.7 Are There Polynomial Circuits for all Problems in NP 214
15 Communication Complexity 219
15.1 The Communication Game 219
15.2 Lower Bounds for Communication Complexity 223
15.3 Nondeterministic Communication Protocols 233
15.4 Randomized Communication Protocols 238
15.5 Communication Complexity and VLSI Circuits 246
15.6 Communication Complexity and Computation Time 247
16 The Complexity of Boolean Functions 251
16.1 Fundamental Considerations 251
16.2 Circuit Size 252
16.3 Circuit Depth 254
16.4 The Size of Depth-Bounded Circuits 259
16.5 The Size of Depth-Bounded Threshold Circuits 264
16.6 The Size of Branching Programs 267
16.7 Reduction Notions 271
Final Comments 277
A Appendix 279
A.1 Orders of Magnitude and O-Notation 279
A.2 Results from Probability Theory 283
References 295
Index 301