计算复杂性理论
判定、优化与不可判定
判定问题只回答“是/否”，优化问题要求最优值或最优方案。很多优化问题可以加入阈值 \(k\) 转成判定形式：
- 图着色：是否能用不超过 \(k\) 种颜色；
- 背包：是否有重量不超过 \(W\)、价值至少为 \(k\) 的方案；
- 最短路：是否存在长度不超过 \(k\) 的路径。
验证一个候选解通常比从头找到它容易，但并非所有判定问题都有算法。
停机问题的反证如下：假设存在 \(H(M,I)\)，能判断程序 \(M\) 在输入 \(I\) 上是否停机。构造程序 \(U(M)\)：若 \(H(M,M)\) 判断会停机，\(U\) 就故意死循环；若判断不停机，\(U\) 就立即结束。把 \(U\) 自身作为输入，无论 \(H(U,U)\) 回答什么都会与 \(U\) 的实际行为矛盾，因此通用停机判定器不存在。
这类自指矛盾与理发师悖论相似。课件还借哥德尔不完备性说明：足够强而自洽的形式系统中，也会存在系统内部既不能证明也不能证伪的命题。
P 与 NP
P 是能由确定性算法在多项式时间内解决的判定问题集合。
NP 是候选证书能在多项式时间内验证的判定问题集合；等价地，可由非确定性计算模型在多项式时间内解决。NP 不是“非多项式”的缩写。
显然
因为能快速求解，就一定能快速验证。是否 \(P=NP\) 至今仍未解决。
Hamilton 路径的候选证书是一串顶点。只需检查起终点、每个顶点是否恰好出现一次，以及相邻顶点之间是否有边，就能在多项式时间内完成验证；但目前不知道一般实例能否在多项式时间内求解。
多项式归约、NP-hard 与 NP-complete
若问题 \(A\) 的任意实例都能在多项式时间内转换为问题 \(B\) 的实例，并保持答案一致，记作
这说明 \(B\) 至少和 \(A\) 一样难。用归约证明困难性时，方向不能写反。
若对所有 \(A\in NP\) 都有 \(A\le_p D\)，则 \(D\) 是 NP-hard。NP-hard 问题不一定属于 NP，甚至不一定是判定问题或可判定问题。
若
则 \(D\) 是 NP-complete。任何一个 NP-complete 问题一旦获得多项式时间算法，所有 NP 问题都可先归约到它再求解，于是 \(P=NP\)。
Hamilton 路径、旅行商、0/1 背包和子集和，应以判定版本讨论 NP-complete；相应的最优化版本通常称为 NP-hard。称 NP-complete 问题“不可处理”依赖于普遍相信的 \(P\ne NP\)，并不是已经证明每个算法都必须指数时间。