复杂度类 NP | Codeboy's Blog

形式陈述

NP 首先是多项式非确定时间的并集：

\mathbf{NP}=\bigcup_{k\ge1}\mathrm{NTIME}(n^k).

因此，一个语言 $L\subseteq\Sigma^*$ 属于 NP，当且仅当某台非确定机器在所有分支均为多项式长度的前提下，以“存在接受分支”判定 $L$ 。这里直接使用了非确定性时间类的统一最坏时间量词。

NP 还有等价的验证器定义。存在多项式 $p$ 和确定性算法

V:\Sigma^*\times\Gamma^*\to\{0,1\},

使 $V$ 对任意 $(x,c)$ 都在 $|x|+|c|$ 的多项式时间内停机，并且

x\in L \iff \exists c\in\Gamma^*:\ |c|\le p(|x|)\ \land\ V(x,c)=1.

从验证器到机器时，非确定地猜至多 $p(|x|)$ 个证书符号，再运行 $V$ 。从机器到验证器时，把每一步采用的非确定选择编码进 $c$ ，确定性重放该分支。固定机器的分支度有限，而分支长度为多项式，所以选择序列也是多项式长度；这给出了两个定义的证明骨架。

直觉

NP 的存在量词只对“是”实例作出承诺：若 $x\in L$ ，至少有一份短证据可以快速检查；若 $x\notin L$ ，所有短候选都会失败。它不是“非多项式时间”的缩写，也没有断言成员问题必须耗费指数时间。

验证器负责核对已经给出的候选，不负责找到候选。非确定机器只是把“存在证书”写成分支语义，并未描述现实硬件如何并行尝试所有字符串。证书方向的这种不对称，正是 NP 与coNP需要分开定义的原因。

例子与边界

对无向图 $G=(V,E)$ ，判定语言 HAM-CYCLE 的证书可以是顶点排列 $(v_1,\ldots,v_{|V|})$ 。验证器先检查每个顶点恰出现一次，再检查

\{v_i,v_{i+1}\}\in E\quad(1\le i<|V|), \qquad \{v_{|V|},v_1\}\in E.

若 $E=\{12,23,34,41,13\}$ ，证书 $(1,2,3,4)$ 逐项通过；而星图 $K_{1,3}$ 的叶子度数为 $1$ ，不可能出现在经过每个顶点一次的环上，因而没有任何排列会通过。验证一个排列只需多项式时间，但定义并未提供寻找该排列的确定性多项式算法。

证书长度必须由输入长度的同一个多项式控制，验证器还须对错误、过长或格式非法的候选正常停机。只说“正确证书上运行很快”不足以证明 NP 成员性；把一个指数长计算历史交给线性时间检查器也不合格，因为证书本身已超出长度预算。

NP 只包含判定语言。搜索任务需要输出见证，通常放在 FNP 等函数类中；优化任务要通过阈值判定语言或专门的优化归约与 NP 联系。某些自归约问题可以借助多次判定调用恢复见证，但这属于额外结构，不是 NP 定义自动赠送的算法。

推论与应用

确定性计算是不分支的非确定性计算，所以 $\mathbf P\subseteq\mathbf{NP}$ ；两者是否相等仍未知。NP 对多项式时间 many-one 归约的逆像封闭：先计算归约结果，再验证目标证书，输出长度与证书长度的多项式复合仍是多项式。

NP 完全性利用这种闭合性识别 NP 内足以承载所有 NP 语言的目标；coNP 则把短证书放在否实例一侧。后续的 PCP、不可近似性和参数化复杂度会改变验证访问方式或算法参数，但阅读它们时仍要保留本页三个基准：对象是编码语言，证书长度按输入长度计，验证器对所有候选都在多项式时间内停机。

参考资料

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, §§2.1–2.2.
Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013, §7.3.