本书全面、系统地介绍了计算复杂性理论的基本内容和基本方法。内容涉及数值计算的复杂性，主要包括Kuhn算法设计、正确性证明和复杂性分析；算法复杂性和计算模型；贪心法、动态规划、回溯法和分枝限界法等问题的算法设计方法以及P类、NP类和NPC类问题及其证明方法、若干NPC问题的近似算法。
　　本书可作为计算机专业及数学专业的本科生或研究生的教材，也可供从事数学和计算机科学的教师和研究人员参考。

无

计算复杂性理论分为两个方面：计算机科学的复杂性理论和数值计算的复杂性理论。
　　数值计算的复杂性理论是计算机科学蓬勃发展的一个必然结果，它主要是研究如何更好地利用机器进行数值计算的问题。对于一种算法，不仅要考虑它是否有收敛性的保证,而且还必须考虑它的计算成本。如果计算成本随问题规模的增加而增加的速度是指数级的，则这种算法将被认为是在实践中难以接受的，因而希望算法的计算成本随问题规模的增加而增加的速度是多项式的。
　　计算机科学的复杂性理论，尤其是其中的NP完全问题是计算机科学理论中最重要的问题。自从1971年S.A.Cook提出P类问题是否等价NP类问题以来，许多著名科学家对这个问题进行了深入研究，有的试图证明它们等价，更多的人猜测并试图证明它们不等价。但迄今为止，人们并没有获得完全的成功，并且越来越多的迹象表明，这是—个十分困难的问题。对该问题的研究带动了对许多其他问题的研究，并逐渐发展成为一个庞大的理论系统。这些研究无论是对增进人们对P和NP本质的了解，还是对许多问题复杂性的解决，都有着重大的意义。
　　本书是在作者多年为电子科技大学计算机专业硕士研究生讲授计算复杂性课程的基础之上经过修改、编写而成的。全书共分九章，前四章主要介绍数值计算的复杂性理论，重点讨论了解代数方程的Kuhn算法。后五章主要介绍计算机科学的复杂性理论，重点是讨论P与NP及NP完全问题。
　　由于作者水平有限，错误和疏漏在所难免，敬请读者批评指正。

作　 者
2004年6月于电子科技大学

顾小丰 孙世新 卢光辉 编著：顾小丰: 1966年出生，1991年于兰州大学数学系获理学硕士学位。现任电子科技大学计算机学院高级工程师，硕士研究生导师。主要从事网络计算及应用、并行计算研究和教学。参与完成了“八五”、“九五”军事预研项目两项，获2001年度“国防科学技术进步奖”二等奖，撰写《离散数学》和《离散数学及其应用》两本教材。
孙世新: 1940年出生，1966年本科毕业于四川大学数学系。现任电子科技大学计算机学院教授，博士研究生导师，享受政府特殊津贴专家，全国并行计算专家委员会委员。 1984年至1987年，法国格勒诺贝尔第一大学计算机与应用数学研究所作访问学者兼客座研究员。 1990年，分别在意大利罗马大学和法国格勒诺贝尔第一大学讲学与工作半年。 1997年2月，香港科技大学计算机系访问与工作。 1999年9月，法国格勒诺贝尔第一大学和贡比涅大学作访问研究。 2000年11月，在香港和马来西亚进行学术访问。 2001年6月到7月，赴美国、加拿大进行学术访问。 2003年7月到8月，赴法国、比利时、德国、瑞典进行学术访问。 主要从事计算机科学理论与应用的研究与教学工作。主要研究方向为网络计算技术、并行/分布式计算及其应用、信息压缩技术、数值计算与组合算法等。主持并参与了“九五”军事预研项目、国家高性能计算基金、“863”计划等多项课题研究。1988年至今，在国内外著名期刊、杂志发表论文70余篇，其中30余篇被国际著名的三大检索系统SCI、EI、ISTP以及美国的著名检索杂志M.R.等收录，出版《组合数学》教材一部。获省科技进步三等奖、“国防科学进步奖”二等奖、校优秀教材奖、优秀论文奖和“摩托罗拉教师奖教金”和“托普基础课教师奖”等多项奖励。
卢光辉: 男，1971年生，1996年于四川师大数学系获硕士学位，2002年于电子科技大学计算机学院获工学博士学位，现任电子科技大学计算机学院副教授，硕士研究生导师。主要从事网格计算、并行处理、计算机网络和图像处理等方面的科研与教学工作，在一级学报上发表学术论文多篇，参与完成了“九五”军事预研项目一项，获2001年度“国防科学技术进步奖”二等奖。

第一部分　 数值计算的复杂性
第1章　 代数方程和数值计算的复杂性理论简介 1
1.1　 代数方程的不动点迭代算法 1
1.2　 收敛性和复杂性—算法优劣判别的两个层次 9
第2章　 代数方程的Kuhn算法 15
2.1　 剖分法与标号法 15
2.1.1　 剖分法 15
2.1.2　 标号法 17
2.2　 互补轮回算法 19
2.2.1　 互补轮回算法原理 19
2.2.2　 进口出口分析 21
2.3　 Kuhn算法的收敛性（一） 23
2.4　 Kuhn算法的收敛性（二） 27
第3章　 Kuhn算法的效率 35
3.1　 误差估计 35
3.2　 成本估计 37
3.3　 单调性问题 42
3.4　 关于单调性的结果 47
第4章　 牛顿法及其计算复杂性简介 53
第二部分　 计算机科学的复杂性理论
第5章　 算法的计算复杂性和计算模型 57
5.1　 算法及其计算复杂性 57
5.2　 确定型图灵机 59
5.3　 随机存取机 62
5.4　 RAM机的程序的计算复杂性 66
5.5　 图灵机和RAM机的相关性 69
5.6　 PIDGIN　 ALGOL—一种高级语言 71
第6章　 几个“难”问题的算法设计 75
6.1　 贪心法和背包问题 75
6.2　 动态规划和货郎担问题 81
6.3　 回溯法和图的可着色性问题 83
6.4　 分枝限界法和带时限的作业调度问题 90
第7章　 NP完全问题 97
7.1　 判定问题、语言和编码 97
7.2　 多项式变换与可满足性问题 99
7.3　 非确定型图灵机 101
7.4　 NP类 105
7.5　 NP完全问题与Cook定理 108
7.6　 强NP完全问题 112
7.7　 Co-NP类问题 115
7.8　 NP困难问题 116
7.9　 空间复杂性简介 118
第8章　 NP完全性证明 121
8.1　 六个基本的NP完全问题 121
8.1.1　 三元可满足性 122
8.1.2　 三维匹配 124
8.1.3　 节点覆盖和团 127
8.1.4　 哈密顿回路 129
8.1.5　 划分 132
8.2　 NP完全性的证明方法 134
8.2.1　 限制法 135
8.2.2　 局部替换法 137
8.2.3　 分量设计法 141
8.3　 P类问题的证明 143
8.3.1　 二元可满足性问题 144
8.3.2　 偶图的独立集问题 145
第9章　 近似算法 147
9.1　 近似的接近程度衡量 147
9.2　 0-1背包问题 148
9.3　 装箱问题 151
9.4　 图的着色问题 153
9.5　 货郎担问题 155
9.6　 多处理机调度问题 157
参考文献 161