难的问题不是NP
我对NP难题感到困惑。
一些NP难题在NP中称为NP-Complete，有些不在NP中。
例如：暂停问题只是NP-hard，而不是NP-complete。
但为什么它不是NP完全的？ 我的意思是一个问题必须具备哪些属性
“NP-hard但不是NP-完全问题”？
我认为最短的答案是：NP-complete = NP-hard AND在NP中。
因此，为了表明一个问题是NP完全的，你必须证明它既是NP-hard也是NP。 通常情况下，显示NP中的问题非常容易（只需给出非确定性多项式时间算法）。 表明一个问题是NP难的，很难。 因此，即使在NP完整性的证明中，大部分证明都致力于NP硬度。
至于暂停问题，它不能在NP中，因此不是NP完全的。
NP定义的一个事实是，你可以在多项式时间内验证一个NP问题的解。 因此，如果一个问题是NP难题，而不是NP完全问题，那么无法以理论上及时的方式验证问题的解决方案。 这是有道理的，如果你看停机问题。 解决方法是“是”或“否”，您只能通过再次解决原始问题进行验证，这意味着它不在NP中。
NP-hard只是意味着“至少与NP中的问题一样困难”。 NP完全意味着“在NP中，所有NP完全问题都可以归结为这个问题，这个问题可以归结为所有NP完全问题”。
维基百科的文章可能是一个很好的起点，因为它专门谈论停机问题作为其插图之一。
链接地址: http://www.djcxy.com/p/39973.html