扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
宇宙、量子和人类心灵
-
>
考研数学专题练1200题
-
>
希格斯:“上帝粒子”的发明与发现
-
>
神农架叠层石:10多亿年前远古海洋微生物建造的大堡礁
-
>
二十四史天文志校注(上中下)
-
>
声音简史
-
>
浪漫地理学:追寻崇高景观
复杂性理论 版权信息
- ISBN:7030166922
- 条形码:9787030166920 ; 978-7-03-016692-0
- 装帧:精裝本
- 册数:暂无
- 重量:暂无
- 所属分类:>>
复杂性理论 内容简介
本书主要研究决定解决算法问题的必要资源,以及利用可用资源可能得到的结果的界,而对这些界的深入理解可以防止寻求不存在的所谓有效算法。
复杂性理论 目录
1 Introduction
1.1 What Is Complexity Theory?
1.2 Didactic Background
1.3 Overview
1.4 Additional Literature
2 Algorithmic Problems & Their Complexity
2.1 What Are Algorithmic Problems?
2.2 Some Important Algorithmic Problems
2.3 Measuring Computation Time
2.4 The Complexity of Algorithmic Problems
3 Fundamental Complexity Classes
3.1 The Special Role of Polynomial Computation Time
3.2 Randomized Agorithms
3.3 The Fundamental Complexity Classes for Algorithmic Problems
3.4 The Fundamental Complexity Classes for Decision Problems
3.5 Nondeterminism as a Special Case of Randomization
4 Reductions-Algorithmic Relationships Between Problems
4.1 When Are Two Problems Algorithmically Similar?
4.2 Reductions Between Various Vaariants of a Problem
4.3 Reductions Between Related Problems
4.4 Reductions Between Unrelated Problems
4.5 The Special Role of Polynomial Reductions
5 The Theory of NP-Completeness
5.1 Fundamental Considerations
5.2 Problems in NP
5.3 Alternative Characterizations of NP
5.4 Cook s Theorem
6 NP-complete and NP-equivalent Problems
6.1 Fundamental Considerations
6.2 Traveling Salesperson Problems
6.3 Knapsack Problems
6.4 Partitioning and Scheduling Problems
6.5 Clique Problems
6.6 Team Building Problems
6.7 Championship Problems
7 The Complexity Analysis of Problems
7.1 The dividing Line Between Easy and Hard
7.2 Pseudo-polynomial Algorithms and Strong NP-comleteness
7.3 An Overview of the NP-competeness Proofs Considered
8 The Complexity of Approximation Problems-Classical Results
8.1 Complexity Classes
8.2 Approximation Algorithms
8.3 The Gap Technique
8.4 Approximation-Preserving Reductions
8.5 Complete Approximation Problems
9 The Complexity of Black Box Problems
9.1 Black Box Optimization
9.2 Yao s Minimax Principle
9.3 Lower Bounds for Black Box COmplexity
10 Additional Complexity Classes
11 Interactive Proofs
12 The PCP Theorem and the Complexity of Approximation Problems
13 Further Topics From Classical Complexity Theory
14 The Complexity of Non-uniform Problems
15 Communication Complexity
16 The Complexity of Boolean Functions
Final Comments
A Appendix
A.1 Orders of Magnitude and O-Notation
A.2 Results from Probability Theory
References
Index
1.1 What Is Complexity Theory?
1.2 Didactic Background
1.3 Overview
1.4 Additional Literature
2 Algorithmic Problems & Their Complexity
2.1 What Are Algorithmic Problems?
2.2 Some Important Algorithmic Problems
2.3 Measuring Computation Time
2.4 The Complexity of Algorithmic Problems
3 Fundamental Complexity Classes
3.1 The Special Role of Polynomial Computation Time
3.2 Randomized Agorithms
3.3 The Fundamental Complexity Classes for Algorithmic Problems
3.4 The Fundamental Complexity Classes for Decision Problems
3.5 Nondeterminism as a Special Case of Randomization
4 Reductions-Algorithmic Relationships Between Problems
4.1 When Are Two Problems Algorithmically Similar?
4.2 Reductions Between Various Vaariants of a Problem
4.3 Reductions Between Related Problems
4.4 Reductions Between Unrelated Problems
4.5 The Special Role of Polynomial Reductions
5 The Theory of NP-Completeness
5.1 Fundamental Considerations
5.2 Problems in NP
5.3 Alternative Characterizations of NP
5.4 Cook s Theorem
6 NP-complete and NP-equivalent Problems
6.1 Fundamental Considerations
6.2 Traveling Salesperson Problems
6.3 Knapsack Problems
6.4 Partitioning and Scheduling Problems
6.5 Clique Problems
6.6 Team Building Problems
6.7 Championship Problems
7 The Complexity Analysis of Problems
7.1 The dividing Line Between Easy and Hard
7.2 Pseudo-polynomial Algorithms and Strong NP-comleteness
7.3 An Overview of the NP-competeness Proofs Considered
8 The Complexity of Approximation Problems-Classical Results
8.1 Complexity Classes
8.2 Approximation Algorithms
8.3 The Gap Technique
8.4 Approximation-Preserving Reductions
8.5 Complete Approximation Problems
9 The Complexity of Black Box Problems
9.1 Black Box Optimization
9.2 Yao s Minimax Principle
9.3 Lower Bounds for Black Box COmplexity
10 Additional Complexity Classes
11 Interactive Proofs
12 The PCP Theorem and the Complexity of Approximation Problems
13 Further Topics From Classical Complexity Theory
14 The Complexity of Non-uniform Problems
15 Communication Complexity
16 The Complexity of Boolean Functions
Final Comments
A Appendix
A.1 Orders of Magnitude and O-Notation
A.2 Results from Probability Theory
References
Index
展开全部
商品评论(10条)
- 主题:精装影印本,质量快接近原版了
其实复杂性理论是纯粹的数学(不是分析代数拓扑数论那种纯数学),虽然名义上与计算机有点关系。本书古典的复杂性理论的各方面什么bpp,ip,pcp等等基本上都覆盖到了,认真看完这本大致上就可以读文章了。
- 主题:数学名著系列,品质非常好,印刷清晰,纸张也好。这个系列的书对...
数学名著系列,品质非常好,印刷清晰,纸张也好。这个系列的书对提高国内数学教育水平很有帮助。
书友推荐
- >
有舍有得是人生
有舍有得是人生
¥14.9¥45.0 - >
小考拉的故事-套装共3册
小考拉的故事-套装共3册
¥36.7¥68.0 - >
我与地坛
我与地坛
¥15.4¥28.0 - >
烟与镜
烟与镜
¥15.8¥48.0 - >
唐代进士录
唐代进士录
¥20.7¥39.8 - >
二体千字文
二体千字文
¥14.0¥40.0 - >
新文学天穹两巨星--鲁迅与胡适/红烛学术丛书(红烛学术丛书)
新文学天穹两巨星--鲁迅与胡适/红烛学术丛书(红烛学术丛书)
¥9.9¥23.0 - >
随园食单
随园食单
¥15.4¥48.0
本类畅销
-
从一到无穷大
¥27.3¥46 -
数学的魅力;初等数学概念演绎
¥12.5¥22 -
Sobolev空间与变分原理
¥23¥58 -
4.23文创礼盒A款--“作家言我精神状态”
¥42.3¥206 -
4.23文创礼盒B款--“作家言我精神状态”
¥42.3¥206 -
一句顶一万句 (印签版)
¥40.4¥68