计算复杂性导论

　　《计算复杂性导论（精）》可用作计算机专业、计算数学专业的计算机理论课程的教材，也是有关研究人员不可或缺的参考书。计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论。《计算复杂性导论（精）》对计算机科学中这一重要理论做了全面的介绍。其内容包含基本理论，如计算模型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. l  时间与空间                  
 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  计数类＃尸                  
 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  NP-完全优化问题                  
 11. 2  PCP和不可近似性                  
 11. 3  优化问题的归约                  
 11. 4  难近似的优化问题                  
 练习题                  
 第十二章  平均NP-完全性理论                  
 12. l  平均易解性                  
 12. 2  多项式时间归约                  
 12. 3  p-分布                  
 12. 4  平均NP-完全问题                  
 12. 5  扁平分布与随机归约                  
 12. 6  扁平分布下的完全问题                  
 12. 7  可抽样分布                  
 练习题                  
 参考文献                  
 名词索引（汉英对照）