0去购物车结算
购物车中还没有商品,赶紧选购吧!
当前位置: 图书分类 > 数学 > 应用数学 > 复杂性理论

相同语种的商品

浏览历史

复杂性理论


联系编辑
 
标题:
 
内容:
 
联系方式:
 
  
复杂性理论
  • 书号:9787030166920
    作者:(德)韦格纳(Ingo,W.)
  • 外文书名:Complexity Theory
  • 装帧:圆脊精装
    开本:B5
  • 页数:310
    字数:380000
    语种:en
  • 出版社:科学出版社
    出版时间:2006-01-01
  • 所属分类:O22 运筹学
  • 定价: ¥148.00元
    售价: ¥116.92元
  • 图书介质:
    按需印刷

  • 购买数量: 件  缺货,请选择其他介质图书!
  • 商品总价:

相同系列
全选

内容介绍

样章试读

用户评论

全部咨询

样章试读
  • 暂时还没有任何用户评论
总计 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
帮助中心
公司简介
联系我们
常见问题
新手上路
发票制度
积分说明
购物指南
配送方式
配送时间及费用
配送查询说明
配送范围
快递查询
售后服务
退换货说明
退换货流程
投诉或建议
版权声明
经营资质
营业执照
出版社经营许可证