Complexity Theory:Exploring the Limits of Efficient Algorithms

Complexity theory is the theory of determining the necessary
resources for the solution of algorithmic problems and, therefore,
the limits of what is possible with the available resources. An
understanding of these limits prevents the search for non-existing
efficient algorithms. This textbook considers randomization as a key
concept and emphasizes the interplay between theory and practice:

New branches of complexity theory continue to arise in response to
new algorithmic concepts, and its results - such as the theory of NP-
completeness - have influenced the development of all areas of
computer science.

The topics selected have implications for concrete applications, and
the significance of complexity theory for today's computer science is
stressed throughout.

차 례
1 Introduction 1
2 Algorithmic problems & their complexity 11
3 Fundamental complexity classes 25
4 Reductions - algorithmic relationships between problems 43
5 The theory of NP-completeness 63
6 NP-complete and NP-equivalent problems 77
7 The complexity analysis of problems 89
8 The complexity of approximation problems - classical results 99
9 The complexity of black box problems 115
10 Additional complexity classes 127
11 Interactive proofs 145
12 The PCP theorem and the complexity of approximation problems 161
13 Further topics from classical complexity theory 185
14 The complexity of non-uniform problems 201
15 Communication complexity 219