JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
NP-Complete versus NP-Hard | Reply
I think the article has NP-Hard and NP-Complete reversed: It is within the set of NP-Complete problems that any problem can be reduced to any other in polynomial time. NP-Complete problems can also be reduced to NP-Hard problems in polynomial time, but the reverse is not true. Hence, even if an efficient (polynomial) time algorithm is found for an NP-Complete problem, not all NP-Hard problems will be solvable in polynomial time.

- Dr. "Zow"
Re: NP-Complete versus NP-Hard (response to post by drzow) | Reply
hello,
I completed my eng in cse and i remember that have gone through all this topics but i completely forgot all that.but at that time also i was so confised abou these concepts.
Re: NP-Complete versus NP-Hard (response to post by drzow) | Reply
This may have been fixed, as the tutorial currently says:

"In fact, there are quite a few important problems for which the best-known algorithm that produces an optimal answer is insufficiently slow for most purposes. The most famous group of these problems is called NP, which stands for non-deterministic polynomial (don't worry about what that means). When a problem is said to be NP-complete or NP-hard, it mean no one knows a good way to solve them optimally. Furthermore, if someone did figure out an efficient algorithm for one NP-complete problem, that algorithm would be applicable to all NP-complete problems. "

I would still suggest rewriting that last sentence as:
"Furthermore, if someone did figure out an efficient algorithm for one NP-hard problem, that algorithm would be applicable to all NP problems."

That is by the definition of NP-hard. It may also be worth mentioning that NP-complete problems are simply problems which are both in NP, and NP-hard. There may be some confusion, as an NP-hard problem is not necessarily in NP (hence why an efficient solution to one NP-hard problem does not mean an efficient solution exists for another).

Finally, there are problems known to be in NP, but not yet proven to be either in P or NP-hard - thus no one knows an efficient solution to these either, despite not being NP-Complete or NP-hard. But working that into the tutorial would require also mentioning P, the subset of NP for which efficient solutions exist, and I understand it was only meant to be a simple overview.
RSS