计算复杂性理论

当学生时没学懂的地方，教这门课时学懂了；看书时忽略的细节，备课时注意到了；备课时自信能讲好一个定理的证明，上课时挂板了；上课时高调阐述一个得意的观点，回答学生提问时心虚了。十年后，当准备为这门课写自己的教材时，终于知道，关于这门课，知道得太少了。为写教材，花了一年多时间查阅文献，才发现，有个别地方，过去十年一直在误导学生。
解惑之道，是一条往返于细节与真理之间的路。这条路，教师多走几遍，学生就多获益几许。要做到在讲堂上从心所欲，教师须经历读书、教书、写书的全过程。编写本书，有几层考虑。其一，我非常想进一步提高“计算复杂性理论”这门课的课堂教学水平。2020 年秋季学期，当第十几次给高年级本科生和研究生讲授这门课时，我已没了以往的激情，这不是个好兆头。为求改变，我边讲课，边把课上所讲内容写下来。2021 年春季学期，我讲授“计算复杂性理论高等议题”这门课。我对这部分内容远不如我对秋季学期讲的那部分内容熟悉，我还是认真做了讲课笔记。之后的一年，我对这些笔记改头换面，补充了所有课上没讲的证明，增加了不少这门课以前没有涉及的内容，在结构上做了变动，直至后，对这本书的定位也做了些许调整。在本书完稿之前，我已确信我能把这门课讲授得更好。考虑之二，中国的计算机专业教育急需一本系统介绍计算复杂性理论的中文教材。中国的计算机专业教育是全球的专业教育，如果它的学生还要为教材发愁，如果它的学生使用的大多数教材都是国外学者撰写的，我们有什么理由说我们的计算机专业教育是好的。出版社的编辑告诉我，百分之九十五以上的中国学生更愿意使用中文教材。我认为他们有的权利要求好的中文教材，任何一本能解决中国计算机专业教育燃眉之急的教材都值得马上写。考虑之三，高等学校计算机类专业教学指导委员会于2019 年5 月启动了“计算机专业教育丛书”系列，作为该丛书的编委会主任，我有幸与国内计算机专业领域的一些著名学者探讨过撰写中文专业教材的问题，他们中的一些接受了我的邀请，加入了撰写本丛书教材的队伍。受他们的鼓舞，我决定也写一本教材。我觉得，如果我不这样做的话，一定会被认为有点虚伪。曾经犹豫，因为国内有一批教授能写一本比这本更好的计算复杂性理论教材；不再犹豫，因为有一本将被超越的教材总比没有好。当然，还有一些其他考虑。在高校教书近三十年，能有一本自己的教材，既多了一份对所选择的终身职业的敬意，也多了一个与同行交流的话题。
    本书的主要读者群是高年级本科生、硕士生、博士生，以及希望了解（更多）计算复杂性理论的教师和科技工作者。我希望这本书包含足够多的细节，学生在积极参与了课堂学习之后能通过阅读本书的相关章节完全理解有关的定义、定理、证明。我希望这本书自圆其说，读者无须参考任何其他资料就可理解本书的全部内容。这些努力是否成功得由读者裁定。
本书可作为以下课程的主参考书：
（1） 面向高年级本科生、研究生的“计算复杂性理论导论”课程，内容涵盖前3章，可略去第1.6节（但要讲线性加速定理）、第1.20节、第2.10节、第3.6节。若对前3 章内容做了较大删减，第4章的前几节内容也可被涵盖。
（2） 面向研究生的“计算复杂性理论高等议题”课程，内容涵盖第4章（“计算复杂性理论导论”课程讲过的除外）、第5章、第6章。
（3） 面向高年级本科生、研究生的“算法理论”课程，涵盖第4章、第6章中有关随机算法和去随机、近似算法和不可近似性的内容。
（4） 面向高年级本科生、研究生的“计算理论”课程，以第1章的内容为核心，并根据学分多少和授课对象不同做适当补充。
作者在上海交通大学讲授“计算复杂性理论导论”和“计算复杂性理论高等议题”课程多年，也在其他学校讲授过“计算复杂性理论导论”课程。感谢选修这些课的学生，他们的问题总会让我去探究计算复杂性理论的更多细节。特别感谢所有的助教，他们为提高这两门课的教学质量做出了贡献。这两门课的所有电子演示文稿可供读者随意使用，无须征得作者同意。
我希望本书能让读者收获人类智慧，我也期待着收获读者的批评和建议。

傅育熙
二零二三年二月八日
上海交通大学徐汇校区
 

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

第 1 章 计算理论  1 
1.1 图灵机  5 
1.2 时间可构造性 9 
1.3 通用图灵机  10 
1.4 对角线方法  15 
1.5 丘奇-图灵论题 17 
1.6 加速定理 21 
1.7 时间复杂性类  24 
1.8 非确定图灵机  26 
1.9 命题逻辑 29 
1.10 谓词逻辑 32 
1.11 计算的逻辑刻画 34 
1.12 时间谱系定理  37 
1.13 间隙定理 41 
1.14 神谕图灵机 42 
1.15 归约  43 
1.16 空间复杂性类  45 
1.17 对数空间类 49 
1.18 多项式空间类  52 
1.19 对数空间的补封闭性  55 
1.20 TIME(T(n))=SPACE(T(n)) 吗  58 
第 1 章练习 63 
第 2 章 难解性  65 
2.1 可验证性 66
2.2 NP-完全性  68 
2.3 库克-莱文定理 69 
2.4 拉德纳定理  73 
2.5 贝克-吉尔-索罗维定理 76 
2.6 多项式谱系  78 
2.7 谱系的逻辑刻画  80 
2.8 谱系的交替机刻画 82 
2.9 无限谱系假设  86 
2.10 第二层中的完全问题  87 
第 2 章练习 91 
第 3 章 电路复杂性 93 
3.1 电路谱系定理  96 
3.2 一致电路 101 
3.3 P/poly  103 
3.4 并行计算 105 
3.5 P-完全性 109 
3.6 哈斯塔德对换引理  111 
第 3 章练习  117 
第 4 章 随机计算与去随机  119 
4.1 随机算法 121 
4.2 通用哈希函数族 136 
4.3 概率图灵机 139 
4.4 BPP 与 ZPP 141 
4.5 PP 与 #P 146 
4.6 积和式计算 151 
4.7 户田定理 155 
4.8 随机游走 159 
4.9 蒙特卡罗方法  172 
4.9.1 近似采样  175
4.9.2 马尔可夫链蒙特卡罗方法  185 
4.9.3 均混时间  188 
4.10 扩张图与去随机 195 
4.10.1 线性代数相关知识  196 
4.10.2 图的谱 200 
4.10.3 扩张图 207 
4.10.4 扩张图上的随机游走 215 
4.11 扩张图的构造  219 
4.11.1 扩张图的构造算子  220 
4.11.2 固定大小扩张图构造 226 
4.11.3 显式扩张图族  228 
4.12 莱因戈尔德定理 231 
第 4 章练习  234 
第 5 章 交互证明系统  236 
5.1 私币交互证明  239 
5.2 公币交互证明  244 
5.3 IP = PSPACE  252 
5.4 两类系统的等价性  257 
5.5 多证明者交互证明系统  262 
5.5.1 定义  263 
5.5.2 NEXP 的多证明者协议  268 
5.6 多线性性测试算法  273 
5.7 并行重复定理  279 
5.7.1 统计距离、詹森不等式、相对熵 282 
5.7.2 随机变量的近似嵌入 289 
5.7.3 博弈的近似生成 293 
5.7.4 证明的后一步 297 
5.8 单回合双证明者交互系统 298 
第 5 章练习  302
第 6 章 近似计算与不可近似性  304 
6.1 近似算法 307 
6.2 不可近似性 324 
6.3 局部可验证性与不可近似性  327 
6.4 错误放大 331 
6.5 证明思想 334 
6.6 线性增强 339 
6.7 线性归减 343 
6.8 PCP 定理的证明 345 
6.9 布尔函数的分析技术  346 
6.9.1 傅里叶展开式  348 
6.9.2 卷积定理  350 
6.9.3 BLR-测试  351 
6.9.4 长码  353 
6.10 哈斯塔德 3-比特 PCP-定理 357 
6.10.1 哈斯塔德验证器 359 
6.10.2 哈斯塔德算法的可靠性  361 
6.11 阈值定理  364 
第 6 章练习  369 
参考文献 370 
定理索引 371 
图索引 373 
术语索引 374

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

本教材可作为以下课程的主参考书：（1）面向高年级本科生、研究生的“计算复杂性理论导论”课程；（2）面向研究生的“计算复杂性理论高等议题”课章；（3）面向高年级本科生、研究生的“高等算法”课程；（4）面向高年级本科生、研究生的“计算理论”课程。