是什么使得 NP 困难问题不是 NP 完全问题？
我对 NP 难题感到困惑。
有些 NP 难问题属于 NP 问题，称为 NP 完全问题，有些则不属于 NP 问题。
例如：停止问题只是 NP 困难问题，而不是 NP 完全问题。
但为什么它不是 NP 完全的呢？我的意思是问题必须符合什么性质
“NP 困难但不是 NP 完全问题”？
I am having confusion about NP-hard problems.
Some NP-hard problems are in NP which are called NP-Complete and some are not in NP.
For ex : Halting problem is only NP-hard, not NP-complete.
But why it is not NP-complete ? I mean what property should a problem have to qualify as
"NP-hard but not NP-complete problem" ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我认为最短的答案是：NP-complete = NP-hard AND in NP。
因此，要证明一个问题是 NP 完全问题，您必须证明它既是 NP 困难问题又是 NP 问题。通常，表明问题属于 NP 非常容易（只需给出一个非确定性多项式时间算法）。证明一个问题是 NP 困难的，嗯，很难。因此，即使在 NP-完备性证明中，大部分证明也致力于 NP-硬度。
至于停机问题，它不属于 NP 问题，因此不是 NP 完全问题。
I think the shortest answer is: NP-complete = NP-hard AND in NP.
Thus, to show that a problem is NP-complete you must show that it is both NP-hard and in NP. Typically, showing that a problem is in NP is pretty easy (just give a non-deterministic polynomial time algorithm). Showing that a problem is NP-hard is, well, hard. Thus, even in a proof of NP-completeness, most of the proof is dedicated to the NP-hardness.
As for the halting problem, it fails to be in NP, and thus is not NP-complete.
NP 的定义是您可以在多项式时间内验证 NP 问题的解决方案。因此，如果一个问题是 NP 困难问题，但不是 NP 完全问题，则您无法在理论上及时验证该问题的解决方案。如果你看看停机问题，这是有道理的。答案是“是”或“否”，您只能通过再次解决原始问题来验证，这意味着它不属于 NP 问题。
What defines NP is the fact that you can verify a solution of a NP problem in polynomial time. Thus if a problem is NP-hard, but not NP-complete, you can't verify a solution to the problem in a theoretically timely manner. This makes sense if you look at the Halting problem. The solution is either 'yes' or 'no', which you can only verify by solving the original problem again, meaning it's not in NP.
NP-hard 简单的意思是“至少和 NP 中的问题一样难”。 NP完全性的意思是“在NP中，所有NP完全问题都可以归结为这个问题，并且这个问题可以归结为所有NP完全问题”。
维基百科文章可能是一个很好的起点，因为它专门讨论了停止问题它的插图之一。
NP-hard simply means "at least as hard as a problem in NP". NP-complete means "in NP, all NP-complete problems can be reduced to this problem and this problem can be reduced to all NP-complete problems".
The Wikipedia article is probably a good starting point, as it specifically talks about the Halting Problem as one of its illustrations.
简短回答：唯一非 NP 完全的 NP 难题是那些不属于 NP 的问题。
长答案：
现在，这是为什么呢？让我们仔细看看 NP 完全和 NP 困难的定义：
一个问题 X 是 NP 完全的，如果：
它在 NP 中
NP 中的每个问题都可以简化为 X在多项式时间内。
如果问题 X 满足 (2)（(1) 不是必要条件），则它是 NP 难问题。
根据这些定义，很明显可以得出这样的结论：唯一 NP 困难但不是 NP 完全的问题是那些不属于 NP 的问题。
例如，所有不是决策问题的 NP 难题都不是 NP 完全的（因为 NP 根据定义是由决策问题形成的）。特别是旅行商问题的搜索版本：给定城市列表及其成对距离，任务是找到访问每个城市一次并返回出发城市的最短路线。 >
TSP 的搜索版本被证明是 NP 困难的，但由于它不是一个决策问题（你不能通过回答是或否来解决它），它不是 NP 的一部分，因此不能是 NP 完全的。
停止问题是一个决策问题，但它在多项式时间内无法验证（根据定义，问题处于 NP 的第二个要求），这就是为什么它不能是 NP 完全的。
Short answer: The only NP-hard problems which are not NP-complete are the ones which are not part of NP.
Long answer:
Now, why is that? Let's look at the definition of NP-complete and NP-hard carefully:
A problem X is NP-complete if:
It is in NP
Every problem in NP is reducible to X in polynomial time.
A problem X is NP-hard if it satisfies (2) ((1) is not a necessary condition).
Out of these definitions it's obvious to conclude that the only problems which are NP-hard but not NP-complete are the ones out of NP.
For instance, all the NP-hard problems which are not decision problems are not NP-complete (since NP by definition is formed with decision problems). In particular, the search version of the Travelling Salesman problem: Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city.
The search version of the TSP is proven to be NP-hard, but since it's not a decision problem (you cannot solve it by answering yes or no to a question) it's not part of NP and thus cannot be NP-complete.
The halting problem is a decision problem, but it's not verifiable in polymonial time (the second requirement for a problem to be in NP by definition) that's why it cannot be NP-complete.