形式陈述

语言 $B$$B$ 称为 NP-hard，若

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

即 NP 中每个语言都能通过多项式时间 many-one 归约转换到 $B$$B$。定义本身不要求 $B\in\mathrm{NP}$$B\in \mathrm{NP}$，甚至不要求 $B$$B$ 可判定。

直觉

NP-hard 表示目标问题至少承载 NP 中所有问题的困难性：一旦能高效解决目标问题，就能在归约开销后高效解决全部 NP 问题。

例子与边界

证明 $B$$B$ NP-hard 时，应从已知 NP-hard 问题 $A$$A$ 构造 $A\le_m^p B$$A{\le }_m^{p}B$；若只证明 $B\le_m^p A$$B{\le }_m^{p}A$，只能说明 $B$$B$ 不比 $A$$A$ 更难。优化问题可称 NP-hard，但这里的形式定义先针对判定语言。

推论与应用

NP-hardness 是下界式分类工具。它与“实际运行慢”不同，也不等于已证明没有多项式算法；若 $\mathrm P=\mathrm{NP}$$\mathrm{P}=\mathrm{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。