计算复杂性导论

2002-8  

高等教育出版社  

堵丁柱,葛可一,王洁  

378  

无  

计算复杂性是计算机理论中极其重要的一个领域。它不但包含了一个完整独立而且内容丰富的理论，同时也对许多其它有关的计算机和应用数学领域产生了重大的影响。计算复杂性理论发源于20世纪60年代，以有多项式时间上界的图灵机为基本计算模型而奠定了理论基础。在70年代初，这门学问由于NP一完全问题的发现而吸引了人们的注意。简单地说，如果一个问题无法在多项式时间内被确定型图灵机解决，我们称它为难解问题。NP一完全问题就是一类直观上难解可是又找不出方法来证明它们的确难解的计算问题.从数学的角度来说，这和其它历史上有名的数学问题一样，给予人们一个智力上重大的挑战。而更重要的是，在无数与计算有关的学术领域里，NP完全问题以各种不同形式层出不穷。因此，这并不是一个纯粹的与世独立的智力游戏，而是对计算机科学有全面影响力的问题。人们在70年代开始对NP完全问题的研究主要是横向发展，也就是以许多不同的计算模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应用。最显著的一个例子就是计算密码学的革命性突破：基于NP问题的公钥密码体系。另一个有名的例子是线性规划的多项式时间解的发现。

计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论。本书对计算机科学中这一重要理论做了全面的介绍。其内容包含基本理论，如计算模型NP-完全性，以及较深入的课题，如线路复杂性、概率复杂性和交互证明系统等。此外，本书还包括了复杂性理论近年来两个较重大的突破，即概率可验证明及其在近似算法上的应用和平均NP-完全理论。本书中所有结果均有严格的数学证明，在每章后配有相关练习题。 本书可用作计算机专业、计算数学专业的计算机理论课程的教材，也是有关研究人员不可或缺的参考书。

堵丁柱，1948年生。中国科学院应用数学所运筹学硕士（1981）。美国加里福利亚大学圣巴巴拉分校数学博士（1985）。美国伯克利数学科学研究所博士后（1985.1986）。美国麻省理工学院助理教授（1986－1987）。美国普林斯顿大学访问学者（1990－1991）。现任美国明尼苏达大学计算机科学系教授，中国科学院应用数学所研究员。Journal 0f Combinatorial Optimization主编，Book Series ofCombinatorial Optimization和Book Series of Networks Theory and Applications主编。主要研究方向为组合优化，计算复杂性，算法分析与设计，计算机和通讯网络。发表论文130篇，著书7本。1993年获中国科学院自然科学一等奖。1995年获中国自然科学二等奖。1998年获美国运筹和管理学会CSTC奖（计算机与运筹学边缘科学奖）。葛可一，1950年生。台湾新竹清华大学数学学士（1972）。美国俄亥俄州立大学数学硕士（1974），计算机科学博士（1979）。现任美国纽约州立大学石溪分校计算机科学系教授.SIAM Journal on Computing与Journal of Complexity编辑。曾主持多项美国自然科学基金会研究课题。主要研究方向为计算复杂性理论，数值计算复杂性和可计算性理论。发表论文55篇，著书3本。王杰，1961年生。中山大学计算机科学系计算数学专业学士（1982），软件专业硕士（1984），美国波士顿大学计算机科学博士（1990）。现任美国麻萨诸塞大学罗威尔分校计算机科学系教授，并任网络与系统安全实验室主任。主要研究方向为平均计算复杂性理论，网络与系统安全，应用算法。曾主持多项美国自然科学基金会的课题及美国英特尔（Intel）公司的课题。发表论文70篇及编书两本。1991年获美国自然科学基金会科研启动奖，2002年获英特尔公司大学项目IXA研究奖。

前言第一章 计算模型 1.1 符号行，编码和布尔函数 1.2 确定型图灵机 1.3 非确定型图灵机 练习题第二章 计算复杂性类 2.1 时间与空间 2.2 通用图灵机 2.3 对角线方法 2.4 模拟 练习题第三章 NP-完全问题 3.1 NP 3.2 Cook定理 3.3 NP-完全问题的例子 3.4 多项式时间图灵归约 练习题第四章 多项式时间分层和多项式空间 4.1 非确定型带神喻图灵机 4.2 多项式时间分层 4.3 PH中的完全问题 4.4 交替图灵机 4.5 PSPACE-完全问题 练习题第五章 线路复杂性 5.1 布尔线路 5.2 单调递增函数与单调线路 5.3 奇偶性函数与深度有界线路 5.4 多项式规模布尔线路 练习题第六章 NP类的结构 6.1 NP中的非完全问题 6.2 单向函数及其在密码学中的应用 6.3 NC 6.4 P-完全性 6.5 NP-完全问题的密度 6.6 EXP-完全问题的密度 练习题第七章 概率机与复杂性类 7.1 随机算法 7.2 概率图灵机及其时间复杂性 7.3 带有界误差的概率机 7.4 BPP，NP和多项式时间分层 练习题第八章 计数复杂性 8.1 计数类#P 8.2 #P-完全问题 8.3 ■P和多项式时间分层 8.4 #P和多项式时间分层 练习题第九章 交互证明系统 9.1 例子与定义 9.2 亚瑟默林证明系统 9.3 AM分层与多项式时间分层 9.4 IP与AM 9.5 IP与PSPACE 练习题第十章 概率可验证明 10.1 PCP的定义 10.2 NEXPPOLY的PCP特征 10.2.1 主要证明 10.2.2 多重线性测试系统 10.2.3 和检验系统 10.3 NP的PCP特征 10.3.1 使用O(logn)个随机数码的PCP系统 10.3.2 低阶测试系统 10.3.3 两个PCP系统的复合 10.3.4 阅读常数多神喻数码的PCP系统 练习题第十一章 近似解的复杂性 11.1 胆完全优化问题 11.2 PCP和不可近似性 11.3 优化问题的归约 11.4 难近似的优化问题 练习题第十二章 平均NP-完全性理论 12.1 平均易解性 12.2 多项式时间归约 12.3 p-分布 12.4 平均NP-完全问题 12.5 扁平分布与随机归约 12.6 扁平分布下的完全问题 12.7 可抽样分布 练习题参考文献名词索引(汉英对照)

插图：

《计算复杂性导论》由高等教育出版社出版。

无

计算复杂性导论 PDF格式下载

复杂性理论是计算机理论研究非常重要的一部分。它以图灵机为基础，由此而衍生出很多东西。但是国内介绍复杂性理论的书非常少，我只看到了这一本。总体感觉很全面，每章之后还有习题。NP完全问题、布尔电路、零知识证明等等，在这本书里都有介绍，不错。

国内唯一一本称得上是详细介绍计算复杂性方面的著作，但有一定难度

注意第十章和十二章，是未来计算数学研究中可值得持续研究的问题。

值得一看的专业书

对我学习非常有帮助

挺好的书，值得拥有！！！

可以收藏，作为参考书。

这书发过来就坏的，希望以后发书注意点，不然会影响你们的形象。退货太麻烦，不退的话这书翻不了多少次肯定全散了，太可恶了！

有点老了，还是挺好的一本书

是学密码的必用的教材,倒是强烈要求我学习,但内容有点难.

内容涵盖的比较广泛，而且许多内容非常前沿，连许多国外的计算复杂度书都不曾涉及，许多内容相当深，如果不是有一定的计算理论基础这本书是啃不动的。不错的案头参考书。