NP不完整的NP难问题难度更大吗？

Question

根据我的理解,所有NP完全问题都是NP难的,但已知一些NP难问题不是NP完全的,NP难问题至少与NP完全问题一样难.

这是否意味着非NP完全的NP难问题更难？它是如何变得更难？

Answer 1

要回答这个问题,首先需要了解哪些NP难题也是NP完全的.如果NP难问题属于集合NP,则它是NP完全的.属于集合NP,需要有一个问题

(i)决策问题,
(ii)问题的解决方案的数量应该是有限的,并且每个解决方案应该是多项式长度,并且
(iii)给定多项式长度解,我们应该能够说出答案是否为问题是是/否

现在,很容易看出可能存在许多NP难问题,这些问题不属于集合NP并且难以解决.作为一个直观的例子,我们需要找到实际时间表的旅行推销员的优化版本比旅行推销员的决策版本更难,我们只需要确定长度<= k的时间表是否存在.

Answer 2

图灵机停机问题在图灵机和NP-hard上是不可判定的,但不是NPC.显然它更难;)

Answer 3

NP难问题的集合是NP完全问题集的超集.复杂类比 NP更"难",例如PSPACE,EXPTIME或EXPSPACE,所有这些都包含NP难但不完全NP完全问题.

Answer 4

图灵停止问题是不可判定的,它属于NP-Hard集.对于turing停止问题,我们没有任何决策,因为它是一种RE语言.所以我们没有任何算法来解决它.因此很明显,NP-Hard集合中也存在无法解决的问题.所以NP-Hard集还包含我们没有任何算法要解决的语言或问题.

Answer 5

还有一些决策问题是 NP 困难的，但不是 NP 完全的，例如停机问题。这是问“给定一个程序及其输入，它会永远运行吗？”的问题。这是一个是/否问题，所以这是一个决策问题。很容易证明停机问题是 NP 困难问题，但不是 NP 完全问题。