News for hackers. Stuff that matters.
Re:P versus NP Explained by gphilip on Monday February 03, 2014 @03:05PM (#7173095)
No, this is not true. But the following is true: if a polynomial-time solution was found for an NP-hard problem, that would mean that all problems in the class NP can be solved in polynomial time [1]. This would include all those NP-hard problems which also happen to be in the class NP.

NP-hard can be read as "as hard to solve as any problem in the class NP". So if we can solve one of these hard problems in polynomial time, then -- by the meaning of NP-hard -- we can solve all problems in the class NP in polynomial time.

The reason why your statement is not true as it is, is that there are NP-hard problems which are not inside the class NP. These problems are "much harder than" any problem in the class NP and so, being able to solve all problems in NP in polynomial time does not mean that these "harder than all of NP" problems can also be solved in polynomial time. Check the Wikipedia entry on NP-hard for an example of such a "harder-than NP, but also NP-hard" problem. https://en.wikipedia.org/wiki/NP-hard

A problem which is both (i) NP-hard, and (ii) in NP is said to be NP-complete. If a polynomial-time solution was found for an NP-hard problem, that would mean that all NP-complete problems can be solved in polynomial time (because they are all in NP).

[1] There is a fine point here turning on what "can be solved" means. If we take "can be solved" to mean "there exists an algorithm", then this statement is fine. Otherwise ... but that is an arcane point anyway.

Re:P versus NP Explained by jmcgough on Monday February 03, 2014 @04:39PM (#7173682)
Thanks for the explanation - I didn't understood the difference between NP-hard and NP-complete when I asked this (the wiki article on NP-hard helped to clarify!).