Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Contents of the monograph

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