NP中的所有问题都不是P NP-complete？

NP中哪些不是P NP-complete？为了让自己更清楚，是NP-P = NPC？如果不是的话，你能举一个既不是P也不是NP-NP的NP问题的例子吗？NP中的所有问题都不是P NP-complete？
NP-hard问题都是NP完全问题吗？

非常感谢您提前。

2017-07-01 user3740951

这可能更适合于其中一个堆栈交换站点。看到这[链接]（https://cs.stackexchange.com/questions/1810/are-there-np-problems-not-in-p-and-not-np-complete）。它似乎回答你的问题。 – pwilcox

我只能回答肯定2.

NP-硬度所需的NP-完整性，如通过它的定义。问题H如果NP中的所有问题都可以在多项式时间内减少到NP-complete，因此，解决NP中硬度定义中的任何其他问题都至少难以解决。

来源

2017-07-01 09:45:58 HeroicKatora

首先，

Problems in NP not known to be in P or NP-complete

它是由拉德纳所示的画面，如果P ≠ NP则存在在NP 既不是在P也不NP-complete问题。这些问题被称为 NP-intermediate问题。 graph isomorphism problem,discrete logarithm problem和integer factorization problem是相信为NP-intermediate的问题的示例。他们是几个NP问题中的一些不知道在P或NP-complete。

NP-hard是一类的其至少硬如在NP的最困难的问题的问题。因此，是的，每NP-complete问题是NP-hard。

来源

2017-07-02 17:38:13 DAle

对于第一个问题，答案取决于P = NP。如果P = NP，那么在NP中没有任何不在P中的问题，所以不存在这样的问题。另一方面，如果NP，则称为Ladner's theorem的结果保证存在NP中的问题，而不是P中的问题，而不是NP-完全的（这些被称为NP-中间问题）。这个定理的证明通过构造符合所有标准的高度人为的语言来工作。我们现在不知道任何具体问题是NP中间值，因为如果我们知道任何我们已经证明了NP的话。

对于第二个问题，是的，根据定义，所有NP完全问题都是NP难题。 NP完全问题被定义为类NP中的NP难问题。

来源

2017-07-02 19:15:49 templatetypedef

NP中的所有问题都不是P NP-complete？

回答

相关问题