为了证明某事是NP-HARD，为什么您需要从NP完成中减少它？

Question

来自Wikipedia：

当且仅当有一个np完整问题l是多项式时间turing-h时，问题h是np- hard（即，h（即，l≤th）。

为什么问题（称其为w）从需要NP完成的需求中减少？为什么它也不能成为NP-HARD？似乎您关心的是“艰难”并不是在NP中。

想法？

Answer 1

它可以。实际上，您的第二段意味着第一段。

假设NP硬性问题H在多项方面可降低到问题X。根据定义，存在一个NP完整问题C，该问题C可降低为H.H。由于两个降低都是多项式的，因此您可以在多项式时间内将C降低到X。因此，在多项式时间内，NP完整问题C可还原为X。因此问题X是NP-HARD。

Answer 2

如果您可以多项式将NP硬问题减少到您的问题上，那么就足以证明您的问题的NP。但是，即使它是NP-HARD本身，特定的NP硬性问题也可能不会多项性地降低。

此外，您不必通过减少来证明NP硬度，您还可以直接证明这一点。