图书介绍
计算机和难解性 NP完全性理论导引PDF|Epub|txt|kindle电子书版本网盘下载
- （美）M.R.加里，D.S.约翰逊著；张立昂等译 著
- 出版社： 北京：科学出版社
- ISBN：7030016793
- 出版时间：1987
- 标注页数：603页
- 文件大小：16MB
- 文件页数：343页
- 主题词：
PDF下载
点此进入-本书在线PDF格式电子书下载【推荐-云解压-方便快捷】直接下载PDF格式图书。移动端-PC端通用种子下载[BT下载速度快]温馨提示：（请使用BT下载软件FDM进行下载）软件下载地址页直链下载[便捷但速度慢] [在线试读本书] [在线获取解压码]
下载说明
计算机和难解性 NP完全性理论导引PDF格式电子书版下载
下载的文件为RAR压缩包。需要使用解压软件进行解压得到PDF格式图书。建议使用BT下载工具Free Download Manager进行下载,简称FDM(免费,没有广告,支持多平台）。本站资源全部打包为BT种子。所以需要使用专业的BT下载软件进行下载。如BitComet qBittorrent uTorrent等BT下载工具。迅雷目前由于本站不是热门资源。不推荐使用！后期资源热门了。安装了迅雷也可以迅雷进行下载！
（文件页数 要大于 标注页数，上中下等多册电子书除外）
注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具
图书目录
第一章 计算机、复杂性和难解性1
1.1 引言1
1.2 问题、算法和复杂性4
1.3 多项式时间算法和难解问题7
1.4 可证的难解问题12
1.5 NP完全问题14
1.6 全书概貌16
第二章 NP完全性理论19
2.1 判定问题、语言和编码方案19
2.2 确定型图灵机和P类26
2.3 非确定型计算和NP类31
2.4 P与NP的关系37
2.5 多项式变换和NP完全性39
2.6 Cook定理45
第三章 NP完全性证明53
3.1 六个基本的NP完全问题53
3.1.1 三元可满足性56
3.1.2 三维匹配59
3.1.3 顶点覆盖和团64
3.1.4 哈密顿回路67
3.1.5 划分72
3.2 NP完全性的证明方法75
3.2.1 限制法76
3.2.2 局部替换法80
3.2.3 分量设计法88
3.3 练习91
第四章 用NP完全性分析问题95
4.1 分析子问题98
4.2 数字问题和强NP完全性111
4.2.1 几个附加定义113
4.2.2 强NP完全性证明118
4.3 把时间复杂性表成自然参数的函数形式131
第五章 NP难度134
5.1 图灵可归约性和NP难的问题134
5.2 术语的历史145
第六章 处理NP完全问题150
6.1 近似算法的性能保证152
6.2 把NP完全性应用于近似问题170
6.3 性能保证和“在实践中”的执行情况184
第七章 NP完全性之外的问题187
7.1 NP的结构187
7.2 多项式谱系196
7.3 计数问题的复杂性205
7.4 多项式空间完全性208
7.5 对数空间218
7.6 难解性证明和P与NP224
附录A NP完全问题汇编231
附录B NP完全性专栏：进展介绍434
参考文献580
名词及问题索引582