Complexity Theory - Exploring the Limits of Efficient
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 | Randomized 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 Randomization | . . . . . . . . . . | 39 |
4 | Reductions - Algorithmic Relationships Between Problems | . . . . . . . . . . | 43 |
4.1 | When Are Two Problems Algorithmically Similar? | . . . . . . . . . . | 43 |
4.2 | Reductions Between Various Variants of a Problem | . . . . . . . . . . | 46 |
4.3 | Reductions Between Related Problems | . . . . . . . . . . | 49 |
4.4 | Reductions 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 Characterizations of NP | . . . . . . . . . . | 69 |
5.4 | Cook s Theorem | . . . . . . . . . . | 70 |
6 | NP-complete and NP-equivalent Problems | . . . . . . . . . . | 77 |
6.1 | Fundamental Considerations | . . . . . . . . . . | 77 |
6.2 | Traveling 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 Reductions | . . . . . . . . . . | 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 | Regarding the Complexity of Graph Isomorphism Problems | . . . . . . . . . . | 148 |
11.4 | Zero-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 Results | . . . . . . . . . . | 173 |
12.4 | The PCP Theorem and APX-Completeness | . . . . . . . . . . | 177 |
13 | Further Topics From Classical Complexity Theory | . . . . . . . . . . | 185 |
13.1 | Overview | . . . . . . . . . . | 185 |
13.2 | Space-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 the Computation Time of Turing Machines | . . . . . . . . . . | 248 |
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 |