不是NP的难题
根据我的理解，所有NP完全问题都是NP难题，但一些NP难题已知不是NP完全问题，NP难问题至少和NP完全问题一样困难。
那是不是NP-NP完全困难的NP难题？ 而且它更难吗？
要回答这个问题，您首先需要了解哪些NP难题也是NP完备的。 如果一个NP难题属于NP集，那么它是NP完全的。 要属于设置NP，需要解决一个问题
（i）决策问题，
（ii）问题解的数量应该是有限的，每个解应该是多项式长度的，并且
（iii）给出一个多项式长度的解，我们应该能够说出问题的答案是/否
现在很容易看出，可能存在许多不属于集合NP且难以解决的NP难问题。 作为一个直观的例子，我们需要找到实际进度表的旅行推销员的优化版本比旅行推销员的决策版本更难，我们需要确定是否存在长度<= k的进度表。
图灵机停机问题在图灵机和NP-hard上是不可判定的，但不是NPC。 显然它更难;）
这套NP难问题是一套NP完全问题的超集。 复杂类比NP更“复杂”，例如PSPACE，EXPTIME或EXPSPACE，所有这些都包含NP-hard但不是NP-complete问题。
链接地址: http://www.djcxy.com/p/6799.html