为什么一些NP-完全问题也是NP-难的？

Question

我试着用一种直观的方式把我听到的P，NP，NP-Complete和NP-Hard包装在一起，这样我就不必记住它们的定义了。

在下图中(左边的场景，P != NP)，NP-Complete和NP-Hard之间有一个重叠区域。这是否意味着有些问题既是NP完全的，又是NP难的？根据这个特殊的答案，我发现这是矛盾的：What are the differences between NP, NP-Complete and NP-Hard?。

上面链接中的表格说，NP-完全问题在多项式时间内是可验证的，而NP-Hard问题是不可验证的。那么怎么会有重叠呢？

​

​

Answer 1

NP -完备性的部分定义是NP难的。因此，每个NP-完全问题都是NP-难的。这也反映在您的两个图表中。

Answer 2

您链接到的表是错误的，直到我在几个小时前修复它。NP -完全问题是NP问题的一个子集，根据定义，所有NP问题在多项式时间内都是可验证的。NP-hard问题是那些至少和任何其他NP问题一样难的问题(这有点不直观，因为不在NP中的问题可能是NP- hard )。

要成为NP-完全问题，必须是

NP

• NP-hard

中的

要在特定的复杂性类中完成，问题必须是

复杂性类中的

2. 至少和复杂性类

中的任何其他问题一样难

我们必须定义“至少一样难”。假设我们在NP中有一个问题A。为了证明它是NP -困难的(因此是NP-完全的)，我们证明了NP中的所有问题都可以在多项式时间内转化为A。因为A至少需要多项式时间来求解，并且多项式在加法下是封闭的，所以转换现在可以忽略不计，并且运行时与A的运行时相同(就其是否为多项式而言)。

一旦你有了一个NP -完全问题，你就可以通过在多项式时间内将另一个NP-完全问题B转化为A来证明在NP中的问题A是NP-困难的(因此是NP-完全的)。

我希望这能说明NP-Complete是NP-hard的一个子集(而且您所链接的表是错误的)。