Joh*_*zzo 0 algorithm complexity-theory computer-science np-complete np
我试图理解P,NP,NP-Complete和NP-Hard之间的关系.
我相信我开始理解一般的想法但是,我对这个问题感到困惑(见标题).
什么是这是一个问题的例子并不 P中时间内可解,是在P个时间核查的,但不是 NP完全？
如果我缺少一些理解,请填写我.
提前致谢
如评论中所述,这是该问题的错误网站.但是,可以简单回答:
什么是在P时间内无法解决的问题的例子,在P时间内是可验证的,但不是NP完全的？
如果我理解你,你想要的是(1)不在P中,(2)在NP中,以及(3)不在NPC中的问题.这些问题是NP中间(NPI)问题.
目前尚不清楚是否存在这样的问题,因为不知道P = NP.
如果P = NP那么显然没有这样的问题; 如果P = NP则P = NPC,因此在P时间内可以验证的每个问题都在P,NP和NPC中,因为它们是相等的.
如果P = NP则已知有!有这样的问题; 至少有一个存在.不幸的是,如果P!= NP,我们不知道我们在NPI中遇到的任何现实问题.可在此处找到可能的候选人列表:
https://en.wikipedia.org/wiki/NP-intermediate
简而言之:知道NPI是否为空等同于解决证明P!= NP,所以开始破解!如果你能找到一个肯定存在于NP中但绝对不属于P或NPC的问题,那么就有很多奖金在等着你.
| 归档时间： |
|
| 查看次数： |
266 次 |
| 最近记录： |