hard problem not to be an 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" ?
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.
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 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.
链接地址: http://www.djcxy.com/p/39974.html上一篇: NP的多项式时间算法
下一篇: 难的问题不是NP