计算理论

计算理论研究算法的能力与限制。可计算性判断是否存在对所有输入都正确终止的算法；复杂度理论在算法存在的前提下，研究时间、空间、通信和查询等资源需求。

问题的编码、计算模型和资源计数方式都是结论的一部分。例如，比较排序的 $\Omega(n\log n)$ 下界只约束比较模型；SAT 的 NP 完备性说明其多项式时间算法会导致 $\mathsf P=\mathsf{NP}$ ，并未证明 SAT 需要指数时间。

预备知识与记号

需要集合、逻辑、渐进复杂度、基础概率及基本算法知识；电路与量子部分还涉及线性代数。

字母表 $\Sigma$ 是有限集合， $\Sigma^*$ 表示所有有限字符串。输入 $x$ 的编码长度记为 $|x|$ ，判定语言记为 $L\subseteq\Sigma^*$ 。例如二进制整数 $N$ 的输入长度为 $\Theta(\log N)$ ，执行 $N$ 步对其输入长度而言是指数时间。

复杂度类用 $\mathsf P$ 、 $\mathsf{NP}$ 等符号表示。非一致电路按输入长度分别选取；一致模型则要求存在统一算法生成相应对象。随机算法的概率默认针对固定输入上的内部随机位，输入分布会另行说明。

参考资料

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

计算理论 ​

目录 ​

预备知识与记号 ​

参考资料 ​

计算理论

目录

预备知识与记号

参考资料