• 
  复杂性理论
  ￥116.92元
• 
  数值最优化
  ￥156.42元

无

样章试读

• 暂时还没有任何用户评论

总计 0 个记录，共 1 页。 第一页 上一页 下一页 最末页

全部咨询(共0条问答)

• 暂时还没有任何用户咨询内容

总计 0 个记录，共 1 页。 第一页 上一页 下一页 最末页

用户名：	匿名用户
E-mail：
咨询内容：

• Contents
  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 Ra ndomized 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 Ra ndomization 39
  4 Reductions - AIgorithmic Relationships Between Problems 43
  4.1 When Are Two Problems AIgorithmically Similar 43
  4.2 Reductions Between Various Variants of a Problem 46
  4.3 Reductions Between Rβlated Problems 49
  4.4 Rβductions 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 Characteriz ations of NP 69
  5 4 Cook's Theorem 70
  6 NP-complete and NP-equivalent Problems 77
  6.1 Fundamental Considerations 77
  6.2τ'raveling 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 Rβductions 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 Rβgarding the Complexity of Graph Isomorphism Problems 148
  11.4 Zerφ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 Rβsults 173
  12.4 The PCP Theorem and APX-Completeness 177
  13 Further Topics From Classical Complexity Theory 185
  13.1 Overview 185
  13.2 Spacφ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 Computation Time 247
  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
  Index 301