JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Tutorial Discussions The Importance of Algorithms NP-Complete versus NP-Hard
 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.
 Forums Tutorial Discussions The Importance of Algorithms NP-Complete versus NP-Hard Previous Thread  |  Next Thread