计算复杂性理论9787302627982

傅育熙

1992年获英国曼彻斯特大学计算机博士学位，1994年起任职于上海交通大学计算机系，现为上海交通大学特聘教授，研究领域为理论计算机科学，是国家杰出青年基金获得者、上海市优秀学科带头人、Mathematical Structures inComputer Science的编委。曾任上海交通大学计算机系主任（2000-2009）、软件学院院长（2001-2013）、国务院学位委员会第六届学科评议组成员（2010-2014）、上海市计算机学会理事长（2015-2018）、教育部计算机类专业教学指导委员会副主任（2013-2022）。讲授的“计算复杂性理论”课程获得“2019年度高校计算机专业优秀教师奖励计划”。

第1章 计算理论

1.1图灵机

1.2时间可构造性

1.3通用图灵机

1.4对角线方法

1.5丘奇-图灵论题

1.6加速定理

1.7时间复杂性类

1.8非确定图灵机

1.9命题逻辑

1.10谓词逻辑.

1.11计算的逻辑刻画

1.12时间谱系定理

1.13间隙定理

1.14神谕图灵机

1.15归约

1.16空间复杂性类

1.17对数空间类

1.18多项式空间类

1.19对数空间的补封闭性

1.20 TIME(T(n))=SPACE(T(n))吗.

第1章练习

第2章难解性2.1可验证性

2.2NP-完全性.

2.3库克-莱文定理

2.4拉德纳定理

2.5贝克-吉尔-索罗维定理

2.6多项式谱系.

2.7谱系的逻辑刻画

2.8谱系的交替机刻画

2.9无限谱系假设

2.10第二层中的完全问题

第2章练习

第3章电路复杂性

3.1电路谱系定理

3.2一致电路

3.3P/poly

3.4并行计算

3.5P-完全性.

3.6哈斯塔德对换引理

第3章练习

第4章随机计算与去随机

4.1随机算法

4.2通用哈希函数族

4.3概率图灵机

4.4BPP与ZPP.

4.5PP与P.

4.6积和式计算.

4.7户田定理

4.8随机游走

4.9蒙特卡罗方法

4.9.1近似采样

4.9.2 马尔可夫链蒙特卡罗方法

4.9.3均混时间.

4.10扩张图与去随机

4.10.1线性代数相关知识

4.10.2图的谱

4.10.3扩张图

4.10.4扩张图上的随机游走

4.11扩张图的构造.

4.11.1扩张图的构造算子

4.11.2固定大小扩张图构造

4.11.3显式扩张图族

4.12莱因戈尔德定理

第4章练习

第5章交互证明系统

5.1私币交互证明

5.2公币交互证明

5.3 IP = PSPACE

5.4两类系统的等价性

5.5多证明者交互证明系统

5.5.1定义

5.5.2NEXP的多证明者协议

5.6多线性性测试算法

5.7并行重复定理

5.7.1 统计距离、詹森不等式、相对熵

5.7.2随机变量的近似嵌入

5.7.3博弈的近似生成

5.7.4证明的最后一步

5.8 单回合双证明者交互系统

第5章练习

第6章近似计算与不可近似性

6.1近似算法

6.2不可近似性

6.3局部可验证性与不可近似性

6.4错误放大

6.5证明思想

6.6线性增强

6.7线性归减

6.8PCP定理的证明.

6.9布尔函数的分析技术

6.9.1傅里叶展开式·

6.9.2巻积定理

6.9.3 BLR-测试

6.9.4长码

6.10哈斯塔德3-比特PCP-定理.

6.10.1哈斯塔德验证器

6.10.2哈斯塔德算法的可靠性

6.11阈值定理

第6章练习

参考文献

定理索引

图索引

术语索引

第1章计算理论

计算理论要回答三个问题。第一个问题是：什么是计算？什么问题可以借助机器求解？著名的丢番图方程要求找出整系数多项式方程a12+Q2x空”+…+akI*=0的整数解。希尔伯特第十问题是：是否存在一个计算过程，判定任给的一个丢番图方程是否有整数解?数学家对什么是计算这个问题颇感兴趣。从机械化的角度看，证明过程是一个寻找满足一定数学和逻辑性质的符号串，读者在理解这个证明时，要进行一个形式化验证过程。数学家的兴趣是，证明过程在多大程度上可以机械化。二十世纪上半叶在数学基础和计算基础领域的研究最终达成了共识：计算是一个独立于任何模型的概念，所有计算模型定义的计算都是等价的。建立在这一共识基础上的可计算理论回答了第一个问题。希尔伯特第十问题最终被年青的苏联数学家马蒂雅谢维奇于 1970年解决，他证明了该问题的答案是否定的[158]。若一个问题可以借助于机器求解，我们总会设法让机器代替人类解决该问题，因为与人类相比，机器的优势不言而喻。所以第二个问题是：如何让机器求解一个可计算问题？一台专用设备可以解决某一类特定问题，一台冯·诺依曼体系架构的计算机可以通过预置一段程序来解决指定问题。无论是用专用计算设备还是通用计算设备解题，核心都是算法。算法理论研究的，正是如何让机器解决问题。尽管人类对算法的兴趣历史悠久，但作为一门理论，系统性的研究和理论突破发生在计算机出现之后。一个著名的例子是素数分解。这是数论中一个古老问题，直到2004年，人们才发现这个问题有高效算法[7]。另一个著名的问题是图同构问题。种种迹象表明，这不是个难问题，但一直没有找到它的高效算法。巴柏在2016年发表了图同构问题的一个准多项式时间算法[24]，被发现了一个错误后，巴柏在几天之后公布了一个更新。这些例子，把我们带到了第三个问题：给定一个计算问题，解决该问题需要多少资源？这些资源包括时间、空间，但最根本的资源限制是能量。围棋机器人可以完败人类选手，但在下棋过程中，前者所消耗的总能量远大于后者。信息技术的发展迫使我们思考如何制定更公平（因而也更环保）的游戏规则。以围棋为例，游戏规则应要求博弈双方在博弈过程中的能耗差限制在一个合理的范围。能耗限制是实实在在的。实际应用中，我们关心一个问题是否有可行算法，即它是否有一个多项式时间算法。如果一个可计算问题没有可行解，它就是一个理论上可计算但实际中不可计算的问题，我们得想其他办法。再看一个著名的问题：给定一个图，该图的一个结点覆盖是一个结点子集，图中的任何一条边都与该结点子集中的某结点关联。最小结点覆盖问题要求计算出一个图的极小的结点覆盖集。实际中，这就是探头安装问题，我们希望用最少的探头，监控到一个楼面的所有走廊。遗憾的是，探头安装问题没有可行解。计算复杂性理论研究如何根据解决问题所消耗的资源量对问题进行分类。它试图刻画一个问题的绝对复杂性，即界定解决该问题所需的最小资源，尽管在这方面计算复杂性理论不太成功。它还希望比较不同问题对资源的相对消耗量，在这方面计算复杂性理论非常成功。计算复杂性理论的核心关注就是可行计算，为了可行性，可以在一定范围内牺牲正确性、精度、完全自动化，甚至可以同时牺牲三者[231]。

……

本书是一本介绍计算复杂性理论的基础教材，内容包括时间复杂性、空间复杂性、NP-理论、多项式谱系、电路复杂性、随机计算及去随机、计数复杂性、交互证明系统、PCP定理、近似计算与不可近似性。本书的主要读者群是高年级本科生、硕士生、博士生，以及希望了解(更多)计算复杂性理论的教师和科研工作者。本教材可作为以下课程的主参考书：(1)面向高年级本科生、研究生的“计算复杂性理论导论”课程，内容涵盖前三章；(2)面向研究生的“计算复杂性理论高等议题”课程，内容涵盖后三章；(3)面向高年级本科生、研究生的“高等算法”课程，内容涵盖第4章、第6章中有关随机算法和去随机、近似算法和不可近似性的内容；(4)面向高年级本科生、研究生的“计算理论”课程，以第1章的内容为核心，并根据学分多少和授课对象不同做适当补充。