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 定理理路Cook–Levin 定理Cook–Levin theorem · SAT is NP-complete布尔可满足性问题 SAT 是 NP 完全问题。给出 SAT 的 NP-hardness 后，先在多项式时间内检查输入是否为合法公式编码；不合法时，输出一台固定的永久循环机器与空输入，作为 HALT 的否实例。合法公式 $\phi$ 则映到机器 $M_{\phi }$ 与空输入。$M_{\phi }$ 忽略输入，依次枚举 $\phi$ 的全部赋值；发现满足赋值就停机，全部尝试失败后则永久循环。写出包含 $\phi$ 的机器描述只需多项式时间，并且

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

优化问题需要说明接口 ​

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

数值编码下的弱困难与强困难 ​

讨论数值问题时，必须区分对象结构和整数大小。以显式物品表、作业表或图为结构部分，另记录非负整数参数；二进制表示数值 $M$ 只需 $O(\log (M+1))$ 位。称算法伪多项式，是指在保持结构表示的前提下，把数值参数改成一元编码后，它的运行时间是完整一元输入长度的多项式。等价的常用账本是结构规模与数值总量的多项式，而非二进制总长度的多项式。

在这样的数值问题框架中，强 NP-hard 表示即使将数值限制在结构规模的某个固定多项式范围内，限制后的判定语言仍 NP-hard。必须指出这一限制和仍成立的归约；并非“数比较大所以很难”。如果一个伪多项式算法在上述小数值子族上运行，那么一元输入长度已是结构规模的多项式，算法就会成为该 NP-hard 子族的多项式算法。因此，强 NP-hard 与伪多项式精确算法同时存在会推出 P=NP。

0–1 整数背包是典型的弱 NP-hard 数值问题：它在二进制编码下 NP-hard，却有 完整容量 DP理路复杂度类 PP · Polynomial time能由确定性算法在输入长度的多项式时间内判定的语言集合。所示的伪多项式算法。在 P≠NP 假设下，这也排除了该数值模型中的强困难性。“弱”不是“容易”的同义词，也不能从任何一个指数算法反推出弱困难；困难性仍须有独立归约。不要把“不是强 NP-hard”一般性地当作“必有伪多项式算法”的证明。

这一结论不应与“强多项式算法”混淆。后者讨论算术操作次数对数值编码大小的依赖，并另控中间数位长；它是算法资源保证，而强 NP-hard 是某个数值受限问题仍困难的归约性质。对有理数还必须说明分子、分母和统一缩放的编码，不能把整数参数的一元化定义直接搬过去。

强困难性排除 FPTAS 时还要检查目标值界。已有 缩放条目理路通过缩放构造 FPTASFPTAS via scaling · value scaling FPTAS通过缩放并向下取整数值，把背包的伪多项式动态规划转为对输入规模与精度均多项式的方案。保留了所需的量化论证：在仍困难的整数目标子族上，若 $0\le OPT\le B(N)$ 且 $B$ 为正多项式，选 $\epsilon =1/(2B(N))$，近似误差小于 1，才迫使返回整数值恰等于最优值。单凭名称而忽略目标值和精度编码，并没有完成这个推论。

若 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 路径困难，不能替代这些证明义务。