NP-hardness

定义 Definition

NP-hardness（NP-困难性）是计算复杂性理论中的概念，指某个计算问题至少和 NP 中最难的问题一样难：如果能在多项式时间内解决该问题，就能在多项式时间内解决所有 NP 问题。它常用来说明某类问题很可能不存在高效（多项式时间）算法（除非 P=NP）。
（相关但不同：NP-complete 既是 NP-hard 又属于 NP。）

发音 Pronunciation (IPA)

/ˌɛnˌpiː ˈhɑːrdnəs/

例句 Examples

The paper proves the NP-hardness of the scheduling problem.
论文证明了该排程问题的 NP-困难性。

Despite many heuristics, NP-hardness suggests there may be no polynomial-time algorithm for the general case unless P=NP.
尽管有许多启发式方法，NP-困难性仍暗示一般情形可能不存在多项式时间算法，除非 P=NP。

词源 Etymology

NP 来自 Nondeterministic Polynomial time（非确定性多项式时间），是复杂性类别名；hardness 表示“难度/困难性”。“NP-hard”最早在 1970 年代随 Cook、Karp 等人的工作而广泛使用，用于描述可通过多项式时间归约（polynomial-time reduction）承载 NP 中困难性的那些问题；“NP-hardness”则是对这种性质的名词化表达。

相关词 Related Words

• NP-hard
• NP-complete
• Reduction
• Polynomial-time
• Complexity
• Heuristic
• Approximation
• P-versus-NP

文学与经典著作 Literary Works

• Stephen Cook, “The Complexity of Theorem-Proving Procedures”（1971）——奠定 NP 完全性与相关困难性讨论的基础语境。
• Richard M. Karp, “Reducibility Among Combinatorial Problems”（1972）——通过归约体系系统展示大量组合问题的困难性框架。
• Michael R. Garey & David S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness”（1979）——经典教材与参考书中大量使用并讨论 NP-hard/NP-hardness。
• Christos H. Papadimitriou, “Computational Complexity”（1994）——系统阐述 NP-hardness、归约与复杂性理论核心概念。