big-o - NP 完全问题也是 NP 难题吗？

Question

我们可以说一个 NP 完全问题是一个既属于 NP 又属于 NP-hard 的问题，但是我们是否可以仅仅因为一个问题是 NP-complete 的事实而完全认为一个问题是 NP-hard 的。

示例：我将一个 NP 完全问题简化a为一个问题b。因此，b现在证明问题是NP完全的。我真的可以说它也是 NP-hard 吗？

Answer 1

NP完整性的定义是：

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

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

请注意，您的问题有一个轻微的错误陈述：

示例：我将一个 NP 完全问题简化a为一个问题b。因此，b现在证明问题是NP完全的。

上述结论只有在你已经证明b是 NP 时才成立。如果b它比 NP“更难”，那么它不是NP 完全的。但是请注意，减少足以证明这b是 NP 难的。