Complexity Theory: Exploring the Limits of Efficient Algorithms

Front Cover
Springer Science & Business Media, Apr 11, 2005 - Computers - 308 pages
0 Reviews

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.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction
1
12 Didactic Background
5
13 Overview
6
14 Additional Literature
10
Algorithmic Problems and Their Complexity
11
22 Some Important Algorithmic Problems
13
23 How Is the Computation Time of an Algorithm Measured?
18
24 The Complexity of Algorithmic Problems
22
105 BPP NP and the Polynomial Hierarchy
138
Interactive Proofs
145
112 Interactive Proof Systems
147
113 Regarding the Complexity of Graph Isomorphism Problems
148
114 ZeroKnowledge Proofs
155
The PCP Theorem and the Complexity of Approximation Problems
161
122 The PCP Theorem
164
123 The PCP Theorem and Inapproximability Results
173

Fundamental Complexity Classes
25
32 Randomized Algorithms
27
33 The Fundamental Complexity Classes for Algorithmic Problems
30
34 The Fundamental Complexity Classes for Decision Problems
35
35 Nondeterminism as a Special Case of Randomization
39
Reductions Algorithmic Relationships Between Problems
43
42 Reductions Between Various Variants of a Problem
46
43 Reductions Between Related Problems
49
44 Reductions Between Unrelated Problems
53
45 The Special Role of Polynomial Reductions
60
The Theory of NPCompleteness
63
52 Problems in NP
67
53 Alternative Characterizations of NP
69
54 Cooks Theorem
70
NPcomplete and NPequivalent Problems
77
63 Knapsack Problems
78
64 Partitioning and Scheduling Problems
80
65 Clique Problems
81
66 Team Building Problems
83
67 Championship Problems
85
The Complexity Analysis of Problems
89
72 Pseudopolynomial Algorithms and Strong NPcompleteness
93
73 An Overview of the NPcompleteness Proofs Considered
96
The Complexity of Approximation Problems Classical Results
99
82 Approximation Algorithms
103
83 The Gap Technique
106
84 ApproximationPreserving Reductions
109
85 Complete Approximation Problems
112
The Complexity of Black Box Problems
115
92 Yaos Minimax Principle
118
93 Lower Bounds for Black Box Complexity
120
Additional Complexity Classes and Relationships Between Complexity Classes
127
102 Complexity Classes Within NP and coNP
128
103 Oracle Classes
130
104 The Polynomial Hierarchy
132
124 The PCP Theorem and APXCompleteness
177
Further Topics From Classical Complexity Theory
185
132 SpaceBounded Complexity Classes
186
133 PSPACEcomplete Problems
188
134 Nondeterminism and Determinism in the Context of Bounded Space
191
135 Nondeterminism and Complementation with Precise Space Bounds
193
136 Complexity Classes Within P
195
137 The Complexity of Counting Problems
198
The Complexity of Nonuniform Problems
201
142 The Simulation of Turing Machines By Circuits
204
143 The Simulation of Circuits by Nonuniform Turing Machines
206
144 Branching Programs and Space Bounds
209
145 Polynomial Circuits for Problems in BPP
211
146 Complexity Classes for Computation with Help
212
147 Are There Polynomial Circuits for all Problems in NP?
214
Communication Complexity
219
152 Lower Bounds for Communication Complexity
223
153 Nondeterministic Communication Protocols
233
154 Randomized Communication Protocols
238
155 Communication Complexity and VLSI Circuits
246
156 Communication Complexity and the Computation Time of Turing Machines
247
The Complexity of Boolean Functions
251
162 Circuit Size
252
163 Circuit Depth
254
164 The Size of DepthBounded Circuits
259
165 The Size of DepthBounded Threshold Circuits
264
166 The Size of Branching Programs
267
167 Reduction Notions
271
Final Comments
277
Appendix
279
A2 Results from Probability Theory
283
References
295
Index
301
Copyright

Common terms and phrases

References to this book

About the author (2005)

The author is a full professor at the Computer Science Department of Dortmund University. He is the author of 8 monographs and more than 150 journal and conference articles. He was head of the German youth competition in computer science and has obtained the university medal for excellent teaching. He is an elected member of the German Academy of Sciences and was head of the committee reviewing computer research projects in Germany.