NP完全问题也是NP困难问题吗？

Question

我们可以说一个 NP 完全问题是一个既是 NP 又是 NP 困难的问题，但是我们是否可以仅仅因为一个问题是 NP 完全的事实就认为它是 NP 困难的。

示例：我将 NP 完全问题

a

简化为问题

b

。因此，问题

b

现在被证明是NP完全的。我真的可以说它也是 NP 困难的吗？

Answer 1

NP完备性的定义为：

问题 Q 是 NP 完全的当且仅当 Q 属于 NP 并且 Q 是 NP 难的。

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

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

示例：我将 NP 完全问题

a

简化为问题

b

。因此，问题

b

现在被证明是 NP 完全的。

仅当您证明

b

处于 NP 状态时，上述结论才成立。如果

b

比 NP“更难”，那么它是 not NP 完全的。但请注意，减少足以证明

b

是 NP 难的。