NP-complete问题也是NP-hard吗？

Question

我们可以说，一个NP完全问题是一个NP和NP难的问题，但我们能否仅仅因为它是NP完全的事实而认为问题是NP-hard。

示例：我将一个NP完成问题a减少为问题b。因此，问题b现在被证明是NP完全的。我真的可以说这也是NP难吗？

Answer 1

NP完全性的定义是：

的问题Q是NP完全当且仅当Q是在NP和Q是NP难。

因此，我们可以肯定地说任何NP完全问题根据定义是NP-hard，。

注意，你在你的问题有轻微的口误：

例子：我减少了NP完全问题a一个问题b。因此，问题b现在被证明是NP完全的。

以上结论仅适用于您已将b显示为NP的情况。如果b比NP更“难”，那么它是而不是 NP-complete。但是请注意，减少量足以证明b是NP-hard。