第七章：$\mathsf{P}$、$\mathsf{NP}$ 与完备问题

$\mathsf{NP}$ 的核心不是“问题看起来很难”，而是 yes 实例存在多项式长度、可在多项式时间验证的证据。

Verifier 定义

language $L$ 属于 $\mathsf{NP}$，若存在多项式时间 verifier $V$ 和多项式 $p$，使

$$x\in L \iff \exists y,\ |y|\le p(|x|),\ V(x,y)=1.$$

$y$ 称为 certificate 或 witness。量词只作用于 yes 实例；no 实例要求所有多项式长度 $y$ 均被拒绝。

等价地，$\mathsf{NP}$ 是非确定性图灵机在多项式时间内判定的 language。非确定性分支猜测 $y$，随后执行 verifier。

$\mathsf P$ 与 $\mathsf{NP}$

根据定义可直接得到

$$\mathsf P\subseteq\mathsf{NP},$$

因为确定性算法可以忽略 witness。是否严格包含仍未知。

若 $\mathsf P=\mathsf{NP}$，所有多项式可验证的存在性问题都能多项式时间判定，并可通过 self-reduction 构造 witness。该结论不表示所有计算问题都变得容易：指数输出、不可判定问题和更高复杂度类仍然存在。

Cook–Levin theorem

Cook–Levin theorem 证明 SAT 是 NP-complete。membership 直接来自满足赋值 verifier。hardness 将任意多项式时间非确定性计算编码为 Boolean formula。

设机器在 $T=p(n)$ 步内运行。构造 computation tableau：

$$\begin{array}{cccc} \text{time }0 & \cdots & \text{initial configuration}\\ \text{time }1 & \cdots & \\ \vdots & & \\ \text{time }T & \cdots & \text{accepting configuration} \end{array}$$

变量描述每个时间、位置上的 tape symbol、head 和 state。公式约束：

1. 初始行正确编码输入；
2. 每个位置恰有一个符号和状态；
3. 相邻两行满足局部转移规则；
4. 某行进入接受状态。

局部转移只检查常数大小窗口，因此公式大小为 $\operatorname{poly}(T)$。可满足赋值与接受计算历史一一对应。

完备性证明的两部分

要证明问题 $B$ NP-complete，需要：

1. $B\in\mathsf{NP}$：给出 witness、verifier 和长度界；
2. 已知 NP-hard 问题 $A\le_m^p B$：给出映射、双向正确性和规模界。

只给出从 $B$ 到 SAT 的编码通常证明 membership 或求解方法，不能证明 $B$ 为 NP-hard。

常用源问题包括 3SAT、Clique、Independent Set、Vertex Cover、Hamiltonian Cycle、Subset Sum。选择与目标结构接近的源问题可以减少 gadget。

coNP

定义

$$\mathsf{coNP}=\{L:\overline L\in\mathsf{NP}\}.$$

TAUT 是 coNP-complete：公式对所有赋值为真。$\mathsf{NP}$ 对 yes 实例有短证据，$\mathsf{coNP}$ 对 no 实例有短证据。

是否

$$\mathsf{NP}=\mathsf{coNP}$$

未知。若某 NP-complete 问题也属于 coNP，则 $\mathsf{NP}=\mathsf{coNP}$。通常猜测二者不同。

整数合数性显然属于 NP，素数性也有短证据，后来更已知 PRIMES 属于 P。它说明“未找到算法”与“类之间 separation”需要严格区分。

Polynomial hierarchy

交替存在与全称量词产生 polynomial hierarchy。例如

$$\Sigma_2^P = \{L:\exists y\ \forall z,\ V(x,y,z)=1\},$$

其中 witness 长度和 verifier 时间均为多项式。

层次记为 $\Sigma_k^P,\Pi_k^P$，并定义

$$\mathsf{PH}=\bigcup_{k\ge0}\Sigma_k^P.$$

若某一层等于其补层或相邻层，PH 会 collapse。许多看似较弱的假设，如 NP 具有小非一致线路，也会导致 PH collapse。

Optimization 与 decision

对许多组合优化问题：

• threshold decision 属于 NP；
• exact value 可用对阈值的二分查询求得；
• witness 可用 self-reduction 构造；
• optimization NP-hard 表示多项式算法会导致 $\mathsf P=\mathsf{NP}$。

数值范围若由二进制编码，二分查询次数取决于值域位数。归约到 decision 的效率需要同时分析查询次数和每次实例规模。

条件 lower bound

NP-completeness 只给出条件困难性。更精确假设包括：

• ETH：3SAT 不存在 $2^{o(n)}$ 时间算法；
• SETH：对任意 $\varepsilon>0$，存在 $k$ 使 $k$-SAT 不存在 $(2-\varepsilon)^n$ 算法；
• fine-grained conjecture：OV、3SUM、APSP 等问题不存在特定指数改进。

fine-grained reduction 要保持指数参数，使目标问题的改进能够转化为对假设问题的改进。普通多项式归约通常不足以做到这一点。

本章自测

1. NP verifier 对 no 实例要求什么？
2. Cook–Levin 公式为何保持多项式大小？
3. 从目标问题归约到 SAT 为什么不能证明目标 NP-hard？
4. 若 SAT 属于 coNP，会得到什么类 collapse？
5. NP-completeness 与 ETH lower bound 的结论强度有何差异？

上一章：电路与非一致计算 · 下一章：搜索、计数与证明 →