我对 NP 难题感到困惑。
一些 NP-hard 问题在 NP 中称为 NP-Complete，而有些则不在 NP 中。
例如：停机问题只是 NP-hard，而不是 NP-complete。
但为什么它不是 NP-complete 呢？我的意思是一个问题应该有什么属性才能被称为
“NP-hard但不是 NP-complete 问题”？
问问题
2071 次
4 回答
3
我认为最短的答案是：NP-complete = NP-hard AND in NP。
因此，要证明一个问题是 NP 完全的，你必须证明它既是 NP 难的，又是 NP 的。通常，表明问题存在于 NP 中非常容易（只需给出一个非确定性多项式时间算法）。证明一个问题是 NP-hard 是非常困难的。因此，即使是在证明 NP完备性的过程中，大部分证明都是针对 NP硬度的。
至于停机问题，它不在NP中，因此不是NP完全的。
于 2011-04-14T18:08:23.423 回答
2
定义 NP 的原因是您可以在多项式时间内验证 NP 问题的解决方案。因此，如果一个问题是 NP 难的，但不是 NP 完全的，则您无法在理论上及时验证问题的解决方案。如果您查看停止问题，这是有道理的。解决方案是“是”或“否”，您只能通过再次解决原始问题来验证，这意味着它不在 NP 中。
于 2012-08-08T12:29:41.033 回答
1
NP-hard 仅仅意味着“至少和 NP 中的问题一样难”。NP-complete 的意思是“在 NP 中，所有的 NP-complete 问题都可以归结为这个问题，并且这个问题可以归结为所有的 NP-complete 问题”。
维基百科的文章可能是一个很好的起点，因为它专门讨论了停机问题作为其插图之一。
于 2011-04-14T11:46:35.720 回答
0
简短 的回答：唯一不是 NP 完全的 NP 难题是那些不属于 NP 的问题。
长答案：
现在，这是为什么呢？让我们仔细看一下 NP-complete 和 NP-hard 的定义：
问题 X 是 NP 完全的，如果：
它在 NP
NP 中的每个问题都可以在多项式时间内简化为 X。
如果问题 X 满足 (2) ((1) 不是必要条件)，则它是 NP-hard。
从这些定义中很明显可以得出结论，唯一的问题是 NP 难但不是 NP 完全的问题是 NP 之外的问题。
例如，所有不是决策问题的 NP-hard 问题都不是 NP 完全的（因为根据定义，NP 是由决策问题形成的）。特别是旅行推销员问题的搜索版本：给定一个城市列表及其成对距离，任务是找到最短的可能路线，该路线仅访问每个城市一次并返回到始发城市。
TSP 的搜索版本被证明是 NP 难的，但由于它不是一个决策问题（你不能通过对问题回答是或否来解决它）它不是 NP 的一部分，因此不能是 NP 完全的。
停止问题是一个决策问题，但它在多项式时间内无法验证（根据定义，问题在 NP 中的第二个要求），这就是为什么它不能是 NP 完全的。
于 2013-02-18T00:55:38.367 回答