如果P=NP，那么我们如何说P=NP=NP完全问题？

Question

如果P=NP，那么我们如何说P=NP=NP完全问题？

algorithmtime-complexitynp

4

图片描述

在维基百科上，我找到了这张图。我不明白在假设P=NP的情况下，我们如何得出P=NP=NP完全问题？

- alienCoder

5

此问题似乎不适合本论坛，因为它涉及到 [cs.se] 或者 [cstheory.se]。 - Bernhard Barker

1

为什么这是离题的？P-NP 是程序员应该掌握的非常必要的概念。 - alienCoder

1

[so]通常更适合关于实际代码的问题。有关计算机科学理论的问题最好在上述网站之一进行。这更像是一个“这将更适合那里”的情况，而不是“这绝对不属于这里”的情况。 - Bernhard Barker

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bright-star · Accepted Answer

我不确定这个问题是否适合在堆栈溢出（理论计算机科学）上讨论，但是如图所示，NP-hard是“至少与NP中的问题一样困难”的问题集；这包括在某种意义上比NP更糟糕的问题。

NP完全问题是NP-hard中具有可还原性关系的问题，这些问题已知与NP中的特定问题相关。基本上，可以在多项式时间或更快地将每个问题转换为NP完全问题，就像其他问题一样难。

以下是CLRS中几个很好的片段，说明了这个问题：

类NP包含那些可以在多项式时间内“验证”的问题。什么是可验证性问题？如果我们以某种方式获得解决方案的“证书”，那么我们可以在多项式时间内验证证书是否正确。

非正式地说，如果一个问题在NP类中，并且和NP中的任何问题一样“难”，那么我们称其为NPC问题，也就是NP完全问题。

如果一个可判定语言 L 满足以下条件，则 L 是 NP 完全的：

L 属于 NP
对于 NP 中的每个 L'，L 可以在多项式时间内被归约到 L'。

如果一个语言 L 满足属性 2，但不一定满足属性 1，我们称 L 是 NP 难的。我们还定义 NPC 为 NP 完全语言类。那么这有什么意义呢？嗯，你可以用集合论来解决它：NP 完全是 NP 的子集，如果 P=NP，则 NP 完全是 P 的子集（事实上，在这一点上它们全部相等，因为您可以通过首先将它们更改为您的魔术 P 算法可以处理的内容来解决它们中的任何一个）。NP 难仍然包括一些 NP 完全问题，但还有其他问题在外面，它们只是困难的。