notation - 为了证明某事是 NP 难的，为什么需要从 NP 完全化简到它？

Question

来自维基百科：

问题 H 是 NP 难的当且仅当存在一个 NP 完全问题 L 是多项式时间图灵可约化为 H（即 L ≤ TH）。

为什么问题（称为 W）从需要 NP 完全减少？为什么它也不能是 NP 难的？看起来你关心的是 W 是“硬”的，而不是它在 NP 中。

想法？

Answer 1

它可以。实际上，您的第二段暗示了第一段。

假设 NP-hard 问题 H 可以多项式归约为问题 X。根据定义，存在一个 NP 完全问题 C，可以多项式归约为 H。由于两个归约都是多项式的，因此您可以在多项式时间内将 C 归约为 X。因此，NP 完全问题 C 在多项式时间内可简化为 X。因此问题 X 是 NP 难的。

Answer 2

如果您可以多项式地将 NP-hard 问题简化为您的问题，则足以证明您的问题的 NP-hardness。然而，一个特定的 NP-hard 问题可能无法多项式地简化为您的问题，即使它本身就是 NP-hard。

此外，您不必通过约简来证明 NP 硬度，您也可以直接证明它。