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