来自维基百科:
A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H (i.e., L ≤ TH).
为什么问题(称之为W)从需要减少到NP完全？为什么它不能也是 NP 困难的呢？看起来你关心的是 W 是否“困难”，而不是 NP 中的问题。
想法？
最佳答案
可以。事实上，你的第二段暗示了第一段。
假设 NP 困难问题 H 可以多项式还原为问题 X。根据定义，存在一个 NP 完全问题 C，可以多项式还原为 H。由于两个还原都是多项式，因此可以在多项式时间内将 C 还原为 X。因此，NP完全问题C可以在多项式时间内简化为X。因此问题 X 是 NP 难的。
关于notation - 为了证明某件事是 NP 困难的，为什么需要从 NP 完全简化到它？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3426925/