我对NP-hard问题感到困惑。
一些NP-hard问题属于NP类，被称为NP-Complete问题，而另一些则不属于NP类。
例如：停机问题只是NP-hard问题，而不是NP-complete问题。
但是，为什么它不是NP-complete问题呢？我的意思是，一个问题应该具有什么性质才能够被认定为“NP-hard但不是NP-complete问题”？
什么因素使得一个NP-hard问题不成为NP-complete问题？
5
- Happy Mittal
3
你可能会发现这个网站很有用：http://cstheory.stackexchange.com/ - johnsyweb
它已经在CS Theory SE上被关闭，原因是“太基础”;-) - Joachim Sauer
我并不是在建议迁移，只是提供一些有趣的阅读材料。 - johnsyweb
4个回答
3
我认为最简短的答案是：NP完全= NP难且在NP中。
因此，要证明一个问题是NP完全的，你必须证明它既是NP难的又在NP中。通常，证明一个问题在NP中相当容易（只需给出一个非确定性多项式时间算法）。证明一个问题是NP难的则比较困难。因此，即使在NP完全的证明中，大部分证明都是专门用来证明NP难度的。
至于停机问题，则无法在NP中，因此不是NP完全的。
因此，要证明一个问题是NP完全的，你必须证明它既是NP难的又在NP中。通常，证明一个问题在NP中相当容易（只需给出一个非确定性多项式时间算法）。证明一个问题是NP难的则比较困难。因此，即使在NP完全的证明中，大部分证明都是专门用来证明NP难度的。
至于停机问题，则无法在NP中，因此不是NP完全的。
- Aubrey da Cunha
2
NP问题的定义在于你可以在多项式时间内验证一个NP问题的解决方案。因此，如果一个问题是NP-hard，但不是NP-complete，你就无法在理论上及时验证该问题的解决方案。如果你看看停机问题，这是有意义的。解决方案只能是“是”或“否”，你只能通过再次解决原始问题来验证它，这意味着它不在NP中。
- Clavus
1
NP-hard 简单来说就是“至少和 NP 问题一样难”。NP-complete 意味着“在 NP 中，所有 NP-complete 问题都可以被归约到这个问题上，而这个问题也可以被归约到所有 NP-complete 问题上”。
维基百科文章 可能是一个很好的起点，因为它特别讨论了停机问题作为其中的一个例子。
- Vatine
2
我阅读了维基百科的文章，但并没有完全理解。我的意思是“至少与 NP 问题一样难”，还有什么吗？
同时，NP-难问题也满足这种缩减属性。 - Happy Mittal
所有的NP完全问题都是NP难问题，一些NP难问题比NP完全问题更难（也就是说，它们至少和NP完全问题一样难，但不能转化为/来自NP完全问题）。 - Vatine
0
简短回答：唯一不是NP完全问题的NP难问题是那些不属于NP的问题。
详细回答：
为什么呢？让我们仔细看一下NP完全和NP难的定义：
如果一个问题X是NP完全问题，则：
它在NP中
NP中的每个问题都可以在多项式时间内归约到X。
如果一个问题X满足（2）（（1）不是必要条件），则它是NP难问题。
从这些定义中，很明显可以得出结论：唯一不是NP完全但是NP难的问题是那些不属于NP的问题。
例如，所有不是决策问题的NP难问题都不是NP完全问题（因为NP的定义是由决策问题组成的）。特别地，旅行商问题的搜索版本：给定城市列表及其两两之间的距离，任务是找到访问每个城市恰好一次并返回原始城市的最短路径。
旅行商问题的搜索版本已被证明是NP难题，但由于它不是决策问题（您无法通过回答是或否的问题来解决它），因此它不属于NP范畴，因此也不能成为NP完全问题。
停机问题是一个决策问题，但无法在多项式时间内进行验证（这是定义中使问题成为NP的第二个要求），因此它不能成为NP完全问题。
- fons
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接