Complexity Theory: Exploring the Limits of Efficient Algorithms

COMPLEXITY THEORY: EXPLORING THE LIMITS OF EFFICIENT ALGORITHMS......Page 1
Springerlink......Page 0
Title Page......Page 3
Copyright Page......Page 4
Preface to the Original German Edition......Page 6
Preface to the English Edition......Page 8
Contents......Page 10
1.1 What Is Complexity Theory?......Page 13
1.2 Didactic Background......Page 17
1.3 Overview......Page 18
1.4 Additional Literature......Page 22
2.1 What Are Algorithmic Problems?......Page 23
2.2 Some Important Algorithmic Problems......Page 25
2.3 How Is the Computation Time of an Algorithm Measured?......Page 30
2.4 The Complexity of Algorithmic Problems......Page 34
3.1 The Special Role of Polynomial Computation Time......Page 37
3.2 Randomized Algorithms......Page 39
3.3 The Fundamental Complexity Classes for Algorithmic Problems......Page 42
3.4 The Fundamental Complexity Classes for Decision Problems......Page 47
3.5 Nondeterminism as a Special Case of Randomization......Page 51
4.1 When Are Two Problems Algorithmically Similar?......Page 55
4.2 Reductions Between Various Variants of a Problem......Page 58
4.3 Reductions Between Related Problems......Page 61
4.4 Reductions Between Unrelated Problems......Page 65
4.5 The Special Role of Polynomial Reductions......Page 72
5.1 Fundamental Considerations......Page 75
5.2 Problems in NP......Page 79
5.3 Alternative Characterizations of NP......Page 81
5.4 Cook’s Theorem......Page 82
6.2 Traveling Salesperson Problems......Page 89
6.3 Knapsack Problems......Page 90
6.4 Partitioning and Scheduling Problems......Page 92
6.5 Clique Problems......Page 93
6.6 Team Building Problems......Page 95
6.7 Championship Problems......Page 97
7.1 The Dividing Line Between Easy and Hard Versions of a Problem......Page 101
7.2 Pseudo-polynomial Algorithms and Strong NP-completeness......Page 105
7.3 An Overview of the NP-completeness Proofs Considered......Page 108
8.1 Complexity Classes......Page 111
8.2 Approximation Algorithms......Page 115
8.3 The Gap Technique......Page 118
8.4 Approximation-Preserving Reductions......Page 121
8.5 Complete Approximation Problems......Page 124
9.1 Black Box Optimization......Page 127
9.2 Yao’s Minimax Principle......Page 130
9.3 Lower Bounds for Black Box Complexity......Page 132
10.1 Fundamental Considerations......Page 139
10.2 Complexity Classes Within NP and co-NP......Page 140
10.3 Oracle Classes......Page 142
10.4 The Polynomial Hierarchy......Page 144
10.5 BPP, NP, and the Polynomial Hierarchy......Page 150
11.1 Fundamental Considerations......Page 157
11.2 Interactive Proof Systems......Page 159
11.3 Regarding the Complexity of Graph Isomorphism Problems......Page 160
11.4 Zero-Knowledge Proofs......Page 167
12.1 Randomized Verification of Proofs......Page 173
12.2 The PCP Theorem......Page 176
12.3 The PCP Theorem and Inapproximability Results......Page 185
12.4 The PCP Theorem and APX-Completeness......Page 189
13.1 Overview......Page 197
13.2 Space-Bounded Complexity Classes......Page 198
13.3 PSPACE-complete Problems......Page 200
13.4 Nondeterminism and Determinism in the Context of Bounded Space......Page 203
13.5 Nondeterminism and Complementation with Precise Space Bounds......Page 205
13.6 Complexity Classes Within P......Page 207
13.7 The Complexity of Counting Problems......Page 210
14.1 Fundamental Considerations......Page 213
14.2 The Simulation of Turing Machines By Circuits......Page 216
14.3 The Simulation of Circuits by Non-uniform Turing Machines......Page 218
14.4 Branching Programs and Space Bounds......Page 221
14.5 Polynomial Circuits for Problems in BPP......Page 223
14.6 Complexity Classes for Computation with Help......Page 224
14.7 Are There Polynomial Circuits for all Problems in NP?......Page 226
15.1 The Communication Game......Page 231
15.2 Lower Bounds for Communication Complexity......Page 235
15.3 Nondeterministic Communication Protocols......Page 245
15.4 Randomized Communication Protocols......Page 250
15.5 Communication Complexity and VLSI Circuits......Page 258
15.6 Communication Complexity and the Computation Time of Turing Machines......Page 259
16.1 Fundamental Considerations......Page 263
16.2 Circuit Size......Page 264
16.3 Circuit Depth......Page 266
16.4 The Size of Depth-Bounded Circuits......Page 271
16.5 The Size of Depth-Bounded Threshold Circuits......Page 276
16.6 The Size of Branching Programs......Page 279
16.7 Reduction Notions......Page 283
Final Comments......Page 289
A.1 Orders of Magnitude and O-Notation......Page 291
A.2 Results from Probability Theory......Page 295
References......Page 307
Index......Page 313