NP 完全性

归约像一个不知答案的编译器。若 $A_0{\le }_m^{p}B$，任何 $B$ 判定器都可接在编译器之后解决 $A_0$，所以箭头指向被证明至少同样困难的目标。构件看起来相似、两个程序在测试中都慢，或只有一个方向能从解构造解，都不足以替代这份编译器及其双向证明。

“complete”还把目标限制在 NP 内。HALT 一类问题可以 NP-hard，却因不可判定而不在 NP；普通 NP 语言则可能容易验证但没有承担全部 NP 的已知归约。成员性与困难性分别控制上界、下界，不能用其中一项推测另一项。

从 3-SAT 归约到 Clique ​

给定含 $m$ 个子句、每个子句恰有三个文字的 3-CNF 公式，为每次文字出现建立一个顶点。只在两个顶点来自不同子句且文字不互为否定时连边，并把团大小设为 $k=m$。所得图有 $3m$ 个顶点、至多 $(\genfrac{}{}{0ex}{}{3m}{2})=O(m^2)$ 条边，构造时间是公式长度的多项式。

若公式可满足，从每个子句选一个为真的文字。被同一赋值选中的两个文字不可能互补，且来自不同子句，所以对应顶点两两相连，形成大小为 $m$ 的团。反过来，同一子句的顶点之间没有边，因此大小为 $m$ 的团必须从每个子句恰选一个顶点；边的定义又保证所选文字没有互补对。把这些文字同时设为真并任意补全其他变量，就得到满足赋值。

例如

产生六个文字出现顶点，目标为大小 $2$ 的团。两个子句中的 $y$ 顶点来自不同子句且不冲突，因此相连；选择它们对应赋值 $y=1$，两个子句都满足。这个小实例展示了构造，前一段的反向论证则排除了“不对应任何一致赋值”的额外团。

最后还要证明目标在 NP 中：Clique 的证书是 $k$ 个顶点，验证器检查互异性并逐对查边。若只完成 3-SAT 到 Clique 的构造而漏掉这一步，只能得到 NP-hardness，不能得到 NP-completeness。

结论的边界 ​

NP-complete 是关于编码判定语言和指定归约的分类，不表示每个实例都困难，也不是无条件的指数时间下界。2-SAT 等受限子类可以有多项式算法；启发式在一批实例上耗时指数也不能证明完全性。若把箭头误写成 $B{\le }_m^p{A}_0$，得到的是用已知难题解决 $B$ 的上界，方向恰好相反。

若任何 NP-complete 语言属于 P，则每个 NP 语言都先归约到它再运行多项式判定器，于是 $\mathbf{P}=\mathbf{NP}$。这是一条条件结论，不能倒写成“NP-complete 已被证明没有多项式算法”。

反过来，若假设 P=NP，则每个同时含有固定是实例 $y$ 和否实例 $n$ 的 NP 语言 $B$ 都是 NP-hard：对任意 $A\in \mathrm{NP}=\mathrm{P}$，先判定 $x\in A$，再输出 $y$ 或 $n$。完全性因而依赖复杂度边界与归约，而不是问题表面结构。

Cook–Levin 定理公理库Cook–Levin 定理Cook–Levin theorem · SAT is NP-complete布尔可满足性问题 SAT 是 NP 完全问题。用通用计算编码证明 SAT 是第一个 NP-complete 起点。此后只需沿多项式时间归约公理库多项式时间归约Polynomial-time reduction · Karp reduction用一个多项式时间可计算的变换把问题 A 的实例转换为问题 B 的实例。链传递困难性，并为每个新目标单独核实NP 成员性公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。，无需重复整张计算 tableau。