我正在尝试以一种直观的方式将我听到的P，NP，NP-Complete和NP-Hard包裹起来，以便我不必记住他们的定义 .
在下图中（左手方案，P！= NP），NP-Complete和NP-Hard之间存在重叠区域 . 这是否意味着一些问题既是NP-Complete又是NP-Hard？根据这个特殊答案，我发现这是矛盾的：What are the differences between NP, NP-Complete and NP-Hard? .
上面链接中的表说NP-Complete问题在多项式时间内是可验证的，而NP-Hard问题则不是 . 那怎么会有重叠呢？
2 回答
NP完全性的部分定义是NP难 . 因此，每个NP完全问题都是NP难的 . 这两个图表也反映了这一点 .
你链接的表是错误的，直到我几个小时前修复它 . NP完全问题是NP问题的子集，并且根据定义，所有NP问题在多项式时间内都是可验证的 . NP难问题是那些至少和其他NP问题一样难的问题（这种问题有点不直观，因为NP中没有的问题可能是NP难的） .
要成为NP完全问题必须是
NP中的
要在特定的复杂性类中完成，问题必定是
在那个复杂性类中
至少与复杂性类中的任何其他问题一样难
我们必须定义“至少同样艰难” . 假设我们在NP中遇到问题A.为了证明它是NP难的（因此NP-Complete），我们证明NP中的所有问题都可以在多项式时间内转换为A.因为A至少需要求多项式时间，并且多项式在加法时是闭合的，所以转换现在可以忽略不计，并且运行时与A的运行时相同（就多项式而言是多项式） .
一旦你有一个NP完全问题，你可以通过采用另一个NP完全问题B并在多项式时间内将其转换为A来证明NP中的问题是NP难（因此是NP完全的） .
我希望这清楚地表明NP-Complete是NP-hard的一个子集（并且你链接的表是错误的） .