1 Introduction
2 Algorithmic Problems & Their Complexity
3 Fundamental Complexity Classes
4 Reductions-Algorithmic Relationships Between Problems
5 The Theory of NP-Completeness
6 NP-complete and NP-equivalent Problems
7 The Complexity Analysis of Problems
8 The Complexity of Approximation Problems-Classical Results
9 The Complexity of Black Box Problems
10 Additional Complexity Classes
11 Interactive Proofs
12 The PCP Theorem and the Complexity of Approximation Problems
13 Further Topics From Classical Complexity Theory
14 The Complexity of Non-uniform Problems
15 Communication Complexity
16 The Complexity of Boolean Functions
Final Comments
A Appendix
A.1 Orders of Magnitude and O-Notation
A.2 Results from Probability Theory
References
Index |
