NP 困难性

NP-hard 表示目标足以承载整个 NP：若 $B$ 有确定性多项式判定器，每个 NP 语言都能先翻译成 $B$ 再调用该判定器，于是 P=NP。这个名称没有提供 $B$ 的上界，因而不保证短证书、可判定性或属于任何特定复杂度类。

证明困难性时，箭头要从已知困难源指向新目标。目标看起来组合爆炸、某个程序运行很慢、或启发式经常失败，都不是归约证明；这些观察没有把任意 NP 实例统一编码进目标。

从一个已知困难语言传递困难性 ​

若 $C$ 已知 NP-hard 且 $C{\le }_m^{p}B$，则对任意 $A\in \mathrm{NP}$ 有

归约的传递性于是证明 $B$ NP-hard。反向证明 $B{\le }_m^{p}C$ 只给出使用 $C$ 解决 $B$ 的方法，无法把 $C$ 的下界传回 $B$。

NP-hard 目标可以不可判定 ​

在 Cook–Levin 定理给出 SAT 的 NP-hardness 后，可把公式 $\phi$ 映到机器 $M_{\phi }$ 与空输入。$M_{\phi }$ 忽略输入，依次枚举 $\phi$ 的全部赋值；发现满足赋值就停机，全部尝试失败后则永久循环。写出包含 $\phi$ 的机器描述只需多项式时间，并且

因此 HALT 是 NP-hard，却不可判定，当然不属于 NP。这个例子也表明归约算法只写程序描述，并没有先运行指数枚举来获知答案。

优化问题需要说明接口 ​

旅行商的阈值语言询问“是否存在总权重至多 $K$ 的巡回”，可以直接套用判定语言定义。若有精确最优化算法，计算最优值后与 $K$ 比较即可解决阈值版，所以通常也称旅行商最优化 NP-hard；严格说，这里使用的是从判定到函数输出的归约，而不是把优化任务本身当作 NP 中的语言。

若 NP-hard 语言 $B$ 属于 P，就立即推出 $\mathbf{P}=\mathbf{NP}$；在尚未解决 P 与 NP 之前，NP-hardness 不是无条件的超多项式时间下界。反过来，即使假设 P=NP，也只会让 NP 内的问题拥有多项式算法，不会让 HALT 这类 NP-hard、类外且不可判定的目标变得可解。

若在困难性之外再证明 $B\in \mathrm{NP}$，就得到NP 完全性公理库NP 完全性NP-completeness同时属于 NP 且为 NP-hard 的性质。。近似、参数化、计数和学习问题还需各自保存误差、参数、输出或分布接口的归约；某个训练程序慢或某条精确 ERM 路径困难，不能替代这些证明义务。