如果P = NP那么我们怎么说P = NP = NP-complete？
ali*_*der 2 algorithm time-complexity np
在维基百科中,我找到了这个图.我不知道如何在假设下p = np得到p = np = np-complete？
不确定这是关于堆栈溢出(Theory Comp Sci)的主题,但NP-hard,正如图中正确显示的那样"至少与NP中的那些问题一样难以解决"; 这包括在某种意义上比NP 更糟糕的问题.
NP完全问题是NP-hard中与NP中已知的特定问题具有可还原性关系的问题.基本上,每个可以在多项式时间或更好的情况下转换为NP完全问题的问题与其他问题一样困难.
以下是一些来自CLRS的好片段,用于说明问题:
NP类包含在多项式时间内"可验证"的那些问题.可验证的问题是什么意思？如果我们以某种方式给出了解决方案的"证书",那么我们可以验证证书在问题输入大小的时间多项式中是否正确.
非正式地,一个问题出现在NPC类中 - 我们将其称为NP完全 - 如果它在NP中并且与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完全问题,但是外面还有其他问题,这些问题很难实现.
- 好，我知道了。因此，如果p=np，则np中的每个问题都可以在多项式时间内解决，因此npc中的每个问题也可以在多项式时间内解决。所以p=np=npc。 (2认同)