《计算机和难解性 NP完全性理论导引》求取 ⇩

第一章　计算机、复杂性和难解性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.4P与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

附录ANP完全问题汇编231

附录B　NP完全性专栏：进展介绍434

参考文献580

名词及问题索引582