据我所知,所有NP完全问题都是NP难问题,但其中一些NP难问题已被证明不是NP完全问题,而NP难问题至少与NP完全问题同等难度。
这是否意味着那些不是NP完全问题的NP难问题更难?它们为什么更难?
据我所知,所有NP完全问题都是NP难问题,但其中一些NP难问题已被证明不是NP完全问题,而NP难问题至少与NP完全问题同等难度。
这是否意味着那些不是NP完全问题的NP难问题更难?它们为什么更难?
图灵机停机问题在图灵机上是不可判定的,而且是NP难的,但不是NPC。显然它更难 ;)
图灵停机问题是不可判定的,属于 NP-Hard 集合。对于图灵停机问题,我们没有任何决策器,因为它是一个 RE 语言。因此,很明显无法解决的问题也在 NP-Hard 集合中。因此,NP-Hard 集合还包含我们没有任何算法可以解决的语言或问题。
来源:http://en.wikipedia.org/wiki/NP-hard#Examples
还有一些决策问题是NP-hard但不是NP-complete,例如停机问题。这个问题是问“给定一个程序和它的输入,它会永远运行吗?” 这是一个是/否问题,因此这是一个决策问题。很容易证明停机问题是NP-hard但不是NP-complete。