书 · 1997 · 迈克尔·西普塞（Michael Sipser）

《计算理论导引》

计算机与 AI书单第 16 名

一句话结论

把“能不能算出来”和“能不能高效算出来”分开，再用模型、证明与归约找出计算的边界。

值不值得读完整本？

值得完整读，尤其适合想打牢计算机与 AI 理论基础的读者。它最有价值的训练，是让你分清一个算法的失败、一个问题的困难，以及所有算法都无法跨过的限制。

按1997年正式首版阅读：先看第0章的证明方法，再读第1—2章的自动机与语言；已有离散数学基础，可以略读第0章的基础术语。
第3—5章与第7章应精读：图灵机、可判定性、归约、P与NP构成全书主干。不要只背结论，要能解释构造为什么有效、归约为什么保持答案。
第6章的递归定理、逻辑理论和信息描述，第8—9章的空间复杂度、层次定理与证明方法的限制，适合第二轮细读；首次阅读可以暂缓技术细节。
第10章要掌握近似、随机、交替、交互证明、并行和密码学各自在改变什么条件；复杂证明可以分次消化。
必须配合练习。每个主要部分至少亲手完成一次机器或文法构造、一次不可能性证明、一次归约和一次资源分析；选择题适合检查概念，不能替代证明训练。

核心观点

1. 记忆的组织方式决定机器能识别什么

有限自动机识别正则语言，增加一个栈后，非确定性下推自动机能够识别上下文无关语言。不同模型之间的边界，来自它们能够保留和使用怎样的信息。

为什么：有限自动机只能用有限个状态概括已经读过的内容，因此不同的长前缀必然会落到同一状态。此后遇到相同后缀，机器就无法再区分这些前缀，所以有些需要无限精确计数的任务做不到。栈可以随输入增长而保存信息，并按后进先出的方式进行匹配，因此能够处理许多嵌套结构。子集构造说明，非确定性有限自动机的多个可能状态可以合并成一个确定性状态集合，所以非确定性在这里没有扩大可识别语言的范围。

2. 图灵机为算法提供统一模型，但可计算性不等于效率

图灵机用简单的读写规则描述一般计算；多带、非确定性等变体与标准图灵机具有相同的语言识别能力。丘奇—图灵论题进一步把直观上的有效计算与图灵机计算联系起来。

为什么：一种机器可以把另一种机器的状态、存储内容和位置编码下来，再逐步模拟它的操作。只要这样的模拟能够完成，更复杂的机器形式就未必增加原则上可解的问题。不同模型反复得到相同的可计算范围，为丘奇—图灵论题提供了支持。但直观的“有效方法”不是预先给定的数学对象，因此这一论题不能只靠两个形式模型等价来证明。模拟还可能增加运行时间，所以能力相同并不保证效率相同。

3. 有些问题没有通用算法，归约能把这种限制传递出去

图灵可识别与图灵可判定不同：前者可以在某些否定实例上一直运行，后者必须对所有输入停机回答。对角化证明通用判定器不可能存在，归约则把一个已知难题的限制传递给其他问题。

为什么：程序本身可以编码成输入，因此一个声称能够判断任意程序行为的程序，也必须处理涉及自身的情形。利用它的预测构造一个故意给出相反行为的程序，就会产生矛盾。这说明失败来自任务要求本身，不能靠换一种实现来消除。若能把已知不可判定的问题A有效转换为问题B，并保持答案，那么B的判定器也会成为A的判定器。因此，证明B不可判定时，关键方向是把A归约到B。

4. 容易验证与容易求解之间的距离，由NP完全性连接起来

P描述确定性多项式时间可判定的问题，NP描述肯定实例具有多项式长度证书、且证书能在多项式时间内验证的问题。一个NP完全问题若有多项式时间算法，整个NP就都有这样的算法。

为什么：给定候选答案后，检查它可能只需逐项核对条件；寻找答案却可能面临大量候选，因此验证与求解需要分别定义。多项式时间归约要求转换过程本身足够高效，避免把原问题的困难偷偷放进转换步骤。Cook—Levin定理把非确定性多项式时间计算的过程编码成布尔约束，从而把任意NP问题连接到可满足性问题。后续归约再把这份困难传递给其他问题。这个推理证明的是问题之间的条件关系，并没有证明P不等于NP，也没有证明所有NP问题都需要指数时间。

5. 时间与空间是不同资源，证明它们的下界也有边界

计算复杂度必须说明限制的是时间还是空间；较少空间可以通过重复计算支持很长的运行过程。层次定理证明某些资源增加确实带来更强能力，相对化结果则提醒我们，有些证明方法不足以解决特定问题。

为什么：运行时间用过后无法收回，工作空间却可以反复覆盖，所以探索大量可能性不一定需要同时保存所有分支。深度优先搜索便可以用空间换时间，这也是NP包含于PSPACE的重要直觉。在适当的可构造性和增长条件下，层次定理通过模拟并对角化，构造出超过较小资源限制的问题。但可以分别构造出使P与NP相等或不等的预言机世界，因此对所有这些世界都原样成立的证明方法，不能单独解决通常的P与NP问题。

6. 改变答案要求、验证方式或计算组织，会改变可行性的边界

面对困难问题，还可以研究近似答案、允许小概率出错、交互验证和并行计算。密码学则把某些计算任务的困难当作可以利用的资源，而其安全性需要相应的困难性假设。

为什么：近似算法通过放宽最优性要求，以可证明的质量保证换取效率。随机算法可以在保持受控错误率的同时简化计算，适当的独立重复还能降低错误概率。交互证明让验证者利用随机挑战检查证明者，允许多轮交流后的验证能力可达到PSPACE。并行计算进一步区分总工作量与依赖链长度，因此顺序多项式时间可解并不自动意味着能够高效并行。密码学中的单向函数利用正向易算、逆向难算的不对称，但这种逆向困难不能仅由P不等于NP直接保证。

反对意见

最坏情况不足以解释日常表现（丹尼尔·斯皮尔曼、滕尚华）

斯皮尔曼与滕尚华在平滑分析论文中指出，最坏情况分析和平均情况分析都可能无法充分解释算法的实际成功。他们考察任意输入受到小幅随机扰动后的期望表现，并对所分析的单纯形算法版本给出多项式平滑复杂度。这提醒读者：从本书的最坏情况分类判断实际运行效果，还需要了解输入的结构与扰动条件。

只看输入总长度，会漏掉可以利用的结构（罗德尼·道尼、迈克尔·费洛斯）

道尼与费洛斯在《Fundamentals of Parameterized Complexity》中系统研究参数化复杂度：运行时间若能写成f(k)乘以输入长度的固定次幂，那么当参数k较小时，某些NP困难问题仍可能得到有效的精确求解。顶点覆盖以目标覆盖大小为参数就是典型例子。他们提供了比单纯询问“是否属于P”更细的分析，但也用参数化困难性说明这种办法并非处处有效。

经典模型的效率结论不能直接推广到量子计算（伊桑·伯恩斯坦、乌梅什·瓦齐拉尼）

伯恩斯坦与瓦齐拉尼在《Quantum Complexity Theory》中建立量子复杂度框架，并通过预言机条件下的分离结果，为量子计算可能超过经典随机计算的效率提供证据。这挑战的是“所有合理计算都能被经典机器高效模拟”的推广。论文没有无条件证明BQP不同于BPP，也没有说明量子计算能解决停机问题；阅读本书时应区分可计算性论题与高效模拟的主张。