复杂度类 NP

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

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

Hamilton 环证书 ​

采用简单无向图中环至少含三个不同顶点的约定。对 $G=(V,E)$，验证器先在 $|V|<3$ 时拒绝；其余情形，判定语言 HAM-CYCLE 的证书可以是顶点排列 $(v_1,\dots ,v_{|V|})$。验证器检查每个顶点恰出现一次，再检查

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

证书接口的边界 ​

证书长度必须由输入长度的同一个多项式控制，验证器还须对错误、过长或格式非法的候选正常停机。形式定义只使用长度不超过 $p(|x|)$ 的证书；可把验证器正规化为发现超长就拒绝，使不存在用超长串绕过可靠性的歧义。

Hamilton 环例子里，若图有 $N$ 个顶点，证书要记录 $N$ 个编号，位长度为 $O(N\log N)$，而不是只说“有 $N$ 个对象所以长 $N$”。检查重复编号即使逐对比较也只用多项式时间，因而证明 NP 成员性不依赖最优化的数据结构。只说“正确证书上运行很快”不足以证明 NP 成员性；把一个指数长计算历史交给线性时间检查器也不合格，因为证书本身已超出长度预算。

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

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

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

Fagin 的描述复杂性刻画公理库描述复杂性：ESO、最小不动点与有序结构Descriptive complexity在显式编码的有限结构上，用 ESO 三染色与 LFP 可达性连接逻辑表达和计算复杂性，并说明固定公式及输入顺序的作用。把短证书换成有限结构上若干猜测的关系表，再用固定一阶公式核验。三染色的完整 ESO 句子给出具体实例；固定元数保证关系表长度为多项式，显式域编码保证这个预算相对于输入位长仍成立。