计算理论：模型、资源与不可行性

算法课通常从一个已经明确的问题出发，设计算法并分析复杂度。计算理论继续追问三个前置问题：

1. 问题本身应当怎样形式化？
2. 复杂度结论依赖哪一种计算模型和资源度量？
3. 当更好的算法长期没有出现时，怎样证明它不存在，或者说明现有证明方法为何不足？

本讲义假设读者已经熟悉渐进复杂度、图算法、动态规划、分治、贪心和基础概率。重点不再是构造单个算法，而是建立比较计算问题和证明不可行性的统一语言。

五个分析维度

维度	典型对象	需要明确的内容
计算什么	language、function、search relation、distributional problem	输入、输出、有效实例和正确性条件
谁来计算	自动机、图灵机、RAM、Boolean circuit、通信协议、量子线路	状态、基本操作、uniformity 和输入访问方式
限制什么	时间、空间、电路大小、深度、通信量、查询次数、随机位、证明长度	资源如何计数，以及参数是输入长度还是其他结构量
如何比较	simulation、reduction、completeness	转换保留什么性质，产生多少开销
想证明什么	upper bound、lower bound、separation、barrier	构造算法、排除算法、区分类或解释证明障碍

复杂度陈述只有在五个维度基本明确后才有含义。例如“排序需要 $\Omega(n\log n)$”只对比较模型成立；整数键允许利用位操作时，可以采用不同上界。“SAT 是 NP-complete”说明它代表一类归约意义下的困难问题，但没有证明 SAT 不在 P。

统一记号

• 字母表记为有限集合 $\Sigma$，字符串集合为 $\Sigma^*$；
• 输入 $x$ 的编码长度记为 $|x|$；
• language 是集合 $L\subseteq\Sigma^*$；
• 多项式时间类记为 $\mathsf{P}$，非确定性多项式时间类记为 $\mathsf{NP}$；
• 随机变量使用大写字母，分布族记为 $\mathcal D=\{D_n\}_{n\ge 1}$；
• 复杂度类使用无衬线体，具体问题和语言使用普通数学字体。

编码不是排版细节。若整数 $N$ 以二进制输入，输入长度为 $\Theta(\log N)$；运行 $N$ 步是指数时间。若图以邻接矩阵编码，输入长度与邻接表不同。所有复杂度分析都应首先确定编码及输入长度。

章节结构

章	主题	核心问题
1. 计算问题与编码	language、function、relation、promise、distribution	算法究竟在求解什么对象？
2. 计算模型	automata、TM、RAM、circuit、protocol、quantum circuit	模型允许执行哪些基本操作？
3. 模拟、归约与完备性	simulation、many-one、Turing reduction、completeness	一个问题如何代表另一个问题的困难性？
4. 可计算性与不可判定性	recognizability、halting、diagonalization、Rice theorem	哪些问题根本不存在通用算法？
5. 时间、空间与层次	time/space class、constructibility、hierarchy、tradeoff	增加资源是否严格增加计算能力？
6. 电路与非一致计算	size、depth、uniformity、$\mathsf{AC^0}$、$\mathsf{NC}$	并行性和非一致性如何改变模型？
7. $\mathsf{P}$、$\mathsf{NP}$ 与完备问题	verifier、certificate、Cook–Levin、coNP	可验证性如何形成复杂度类？
8. 搜索、计数与证明	FNP、TFNP、PPAD、PLS、#P、proof system	输出不是一个 bit 时如何定义困难性？
9. 随机化与平均复杂度	RP、BPP、Yao、distributional problem、PRG	随机性改善了什么保证？
10. 通信复杂度	deterministic/randomized protocol、rectangle、discrepancy	输入分散时，信息交换至少需要多少？
11. 查询复杂度	decision tree、adversary、certificate、property testing	只计算输入访问次数能得到哪些 lower bound？
12. 量子计算	qubit、unitary、measurement、BQP、quantum query	量子线路改变了哪些资源界限？
13. Lower bound 与证明障碍	diagonalization、circuit lower bound、relativization、natural proofs、algebrization	为什么主要 separation 如此困难？

证明任务

计算理论中的证明通常属于以下四类。

Upper bound

给出模型中的算法或构造，并证明正确性与资源上界。例如证明 $s$-$t$ reachability 属于 $\mathsf{NL}$，需要给出只保存当前顶点和步数的非确定性算法。

Lower bound

证明所有满足模型限制的算法都至少消耗某项资源。lower bound 必须量化模型中的全部算法，因而通常需要信息论、组合结构、对角化或代数方法。

Separation

证明两个复杂度类不同，例如时间层次定理给出

$$\mathsf{P}\subsetneq\mathsf{EXP}.$$

未解决的 $\mathsf{P}$ 与 $\mathsf{NP}$ 问题也是 separation 问题。

Barrier

证明一类方法不足以解决目标问题。relativization、natural proofs 和 algebrization 不直接给出 $\mathsf{P}$ 与 $\mathsf{NP}$ 的关系，而是约束可能成功的证明技术。

阅读方法

分析每个定理时，建议记录以下信息：

1. 问题类型和输入编码；
2. 计算模型及其 uniformity；
3. 受限资源和渐进参数；
4. 使用的归约或模拟及其开销；
5. 结论是 upper bound、lower bound、separation 还是 barrier；
6. 定理没有排除哪些更强模型或不同资源。

同一个问题在不同模型中可以有完全不同的复杂度。本讲义的目标是使这些限定条件成为结论的一部分，而不是隐藏在定理名称之后。

参考

• Michael Sipser, Introduction to the Theory of Computation
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach
• Oded Goldreich, Computational Complexity: A Conceptual Perspective
• Stasys Jukna, Boolean Function Complexity
• E. Kushilevitz and N. Nisan, Communication Complexity
• Ronald de Wolf, Quantum Computing: Lecture Notes