计算复杂性:P与NP

SAT显然属于NP：一个满足赋值就是一个证书，只需代入数值就能在多项式时间内验证。深刻之处在于证明每个NP问题都归约到SAT——这之所以成立，是因为布尔公式的表达能力足以逐步、逐格、逐时刻地描述任意多项式时间验证器的整个运行过程，于是「是否存在证书」就变成了「这个庞大的公式是否可满足」。

设 $A \in NP$，其多项式时间验证器 $V$ 在长度为 $n$ 的输入配合长度至多为 $n^k$ 的证书上运行时间至多为 $n^k$。固定一个长度为 $n$ 的输入 $x$；我们构造一个布尔公式 $\phi_x$，使其可满足当且仅当存在某个证书能让 $V$ 接受。

设想 $V$ 在 $(x,y)$ 上的整个计算过程（对未知证书 $y$）被排列成一个表格（tableau）：一个 $n^k \times n^k$ 的网格，第 $t$ 行记录验证器在时刻 $t$ 的完整带内容与读写头位置。为每个（单元格、时刻、可能符号）三元组引入一个布尔变量，记录该时刻该单元格所放的符号——由于网格的单元格数与时刻数都是多项式量级，这只是多项式数量的变量。

公式 $\phi_x$ 构造为若干子句的合取（AND），这些子句强制四个局部的、易于检验的条件：(1) 每个时刻每个单元格恰好持有一个符号；(2) 第 $0$ 行正确编码了固定输入 $x$，其后跟着尚待猜测的证书 $y$ 的空白占位；(3) 相邻两个时刻之间每个小窗口内的相邻单元格都与 $V$ 的转移规则一致（正是在这里，第 $0$ 行中自由的证书比特得以影响之后的计算）；(4) 最终时刻的某个单元格记录接受状态。

这些条件中的每一个都只约束变量的一个小的、固定大小的邻域，因此每个条件都转化为常数个子句，而需要约束的邻域个数也只是多项式个——所以 $\phi_x$ 的规模是多项式的，并且能从 $x$ 在多项式时间内计算出来。按此构造，$\phi_x$ 可满足当且仅当存在一个一致的表格，也就是当且仅当存在某个证书 $y$ 使 $V(x,y)$ 接受，也就是当且仅当 $x \in A$。这就展示了对任意 $A \in NP$ 的归约 $A \le_p \text{SAT}$，结合前面证明的 $\text{SAT} \in NP$，就证明了SAT是NP完全的。

$B$ 的NP完全性意味着每个NP问题都可以在多项式时间内被改写为 $B$ 的一个实例。若 $B$ 本身能在多项式时间内求解，将改写步骤与求解步骤串联起来，就同样能在多项式时间内解出原来的NP问题——因此，只要有一个可行的（易解的）NP完全问题，就会把所有NP问题一起拖入P。

设 $B$ 是NP完全的，且存在一个在时间 $O(n^{k_1})$ 内求解 $B$ 的算法。任取 $A \in NP$；由 $B$ 的NP完全性可知 $A \le_p B$，即存在一个在时间 $O(n^{k_2})$ 内可计算的归约函数 $f$，把 $A$ 的实例映射为 $B$ 的实例，同时保持是/否答案不变。

对 $A$ 的一个长度为 $n$ 的输入 $x$，先计算 $f(x)$：这需要时间 $O(n^{k_2})$，特别地输出 $f(x)$ 的长度至多为 $O(n^{k_2})$（多项式时间算法写出的输出不能比其运行时间更长）。然后在 $f(x)$ 上运行求解 $B$ 的多项式时间算法：由于 $|f(x)| = O(n^{k_2})$，这需要时间 $O\big((n^{k_2})^{k_1}\big) = O(n^{k_1 k_2})$。

总运行时间为 $O(n^{k_2}) + O(n^{k_1 k_2}) = O(n^{k_1 k_2})$，仍是关于 $n$ 的多项式（两个多项式的复合仍是多项式）。由归约的正确性，$x$ 是 $A$ 的「是」实例当且仅当 $f(x)$ 是 $B$ 的「是」实例，因此这一组合过程能在多项式时间内正确判定 $A$。

由于 $A \in NP$ 是任意的，每个NP问题都有多项式时间算法，即 $NP \subseteq P$。结合恒成立的包含关系 $P \subseteq NP$，即得 $P = NP$。