## Complexity Theory: Exploring the Limits of Efficient AlgorithmsComplexity 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

### 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 |

295 | |

301 | |