np-hard

NP-hard 是计算复杂性理论中的术语，指至少和 NP 完全问题一样难的问题；它强调问题的计算难度，而不一定说明问题本身属于 NP。

💡 记忆钩子

把 NP-hard 想成一堵“难题墙”：如果能在多项式时间内把某个 NP 完全问题转化为问题 H，那么攻克 H 就至少像攻克 NP 完全问题一样难。这个核心想法可用图灵归约表达；在只讨论判定问题时，也常用多项式时间多对一归约来表达同一类“不会更容易”的关系。

📝 学习建议

先记住“至少和 NP 完全问题一样难”，再区分它与 NP-complete：NP-hard 问题不必属于 NP，也不必能在多项式时间内验证解。
不要把 hard 理解成“目前还没有算法”；它是关于归约关系和计算复杂性的技术标签。

📖 中文释义

adj

core 至少和 NP 完全问题一样难

📖 如果某个 NP 完全问题能够在多项式时间内通过图灵归约转化为问题 H，那么 H 就是 NP-hard。直观地说，解决 H 至少足以应对一个 NP 完全难题，因此 H 不会比 NP 完全问题更容易。

💡 常见句型是“某问题是 NP-hard”或“NP-hard 问题”，后面也可接“通过……归约证明”。这里的“是”表示复杂性分类，不表示该问题一定属于 NP。中文技术写作中不要把它改说成“NP 困难问题”而丢失术语的分类含义。

not-comparable

研究人员证明了这个调度问题是 NP-hard。

研究人员证明了这个调度问题至少和 NP 完全问题一样难。

许多组合优化问题都被认为是 NP-hard 问题。

许多组合优化问题都属于至少和 NP 完全问题一样难的问题。
common 判定问题中的多对一归约定义

📖 在只讨论判定问题时，NP-hard 也常定义为：存在一个 NP 完全问题，能在多项式时间内通过多对一归约转化为问题 H。它仍然表达同一个核心判断——H 至少和 NP 完全问题一样难，只是采用了更受限制的归约方式。

💡 这种用法常出现在复杂性理论教材、定理或形式定义中，尤其是在上下文已经限定“判定问题”时。看到“多项式时间多对一归约”时，不要误以为它是另一种日常意义，而应理解为 NP-hard 的一种常见形式化定义。不同资料的归约约定可能不同，引用定义时应以该资料为准。

not-comparable

在本章中，我们用多项式时间多对一归约定义 NP-hard。

在本章中，我们把 NP-hard 定义为可由 NP 完全问题通过多项式时间多对一归约得到的难度级别。

🏷 单词标签 & 词根