在维基百科中，我找到了这张图。我不明白在假设 p=np 下我们如何得到 p=np=np-complete？
问问题
8127 次
1 回答
8
不确定这是关于堆栈溢出的主题（Theoretical Comp Sci），但 NP-hard，如图中正确显示的是“至少与 NP 中的问题一样难的一组问题”；这包括在某种意义上比 NP更糟糕的问题。
NP 完全问题是 NP-hard 中的那些问题，它们与已知存在于 NP 中的特定问题具有可约性关系。本质上，可以在多项式时间内或更好地转换为 NP 完全问题的每个问题都与其他问题一样难。
以下是来自CLRS的几个很好的片段，它们说明了这个问题：
NP 类由多项式时间内“可验证”的问题组成。我们所说的可验证问题是什么意思？如果我们以某种方式获得了解决方案的“证书”，那么我们可以验证该证书在问题输入大小的时间多项式上是否正确。
非正式地，如果问题属于 NP 并且与 NP 中的任何问题一样“难”，则该问题属于 NPC 类——我们将其称为 NP 完全问题。
一个可判定的语言 L 是 NP 完全的，如果：
- L 在 NP 中，并且
- 对于 NP 中的每个 L'，L' 可以在多项式时间内简化为 L。
如果语言 L 满足属性 2，但不一定满足属性 1，我们说 L 是 NP 难的。我们还将 NPC 定义为 NP 完全语言的类。
（我可能将 L' 和 L 倒置在那里，可还原性符号与用英文阅读的方式相反。）
那么有什么意义呢？好吧，你可以用集合论来解决它：NP-complete 是 NP 的一个子集，如果 P=NP，那么 NP-complete 是 P 的一个子集（事实上，它们在这一点上都变得相等，因为你可以通过首先将它们更改为您的神奇 P 算法可以处理的东西来解决其中的任何一个）。NP-hard 仍然包含一些 NP-complete 问题，但还有其他问题，它们只是hard。
于 2014-02-20T06:53:37.020 回答