形式陈述

语言 $B$$B$ 称为 NP-complete，当且仅当同时满足

$$ B\in\mathrm{NP} \qquad\text{且}\qquad \forall A\in\mathrm{NP},\ A\le_m^p B. $$$$B\in \mathrm{NP}\text{且}\mathrm{\forall }A\in \mathrm{NP},A{\le }_m^{p}B.$$

即 $B$$B$ 既有多项式可验证证书，又是 NP-hard。

直觉

NP-complete 问题位于 NP 内部的“最难层”：它们仍可验证，但任何一个被多项式时间解决都会连带解决整个 NP。

例子与边界

SAT、3-SAT 等是典型 NP-complete 问题。只给出从已知完全问题到 $B$$B$ 的归约可证明 NP-hard，还必须单独证明 $B\in\mathrm{NP}$$B\in \mathrm{NP}$ 才能得到 NP-complete。归约方向不可颠倒。

推论与应用

若任一 NP-complete 语言属于 $\mathrm P$$\mathrm{P}$，则 $\mathrm P=\mathrm{NP}$$\mathrm{P}=\mathrm{NP}$；反之若 $\mathrm P=\mathrm{NP}$$\mathrm{P}=\mathrm{NP}$，每个非平凡 NP 语言都可在通常归约下成为 NP-hard。完全性理论使大量问题共享同一复杂度边界。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，§2.1。
• Richard M. Karp, “Reducibility Among Combinatorial Problems,” in Complexity of Computer Computations, 1972, pp. 85–103，Full chapter。