News for hackers. Stuff that matters.
Re:P versus NP Explained by mjfl on Monday February 03, 2014 @02:48PM (#7172981)
Edit: This might not be true for NP-hard, but I misread your post and assumed you meant NP-complete.

Yes. It is because every problem in NP can be "reduced" (transformed into) an NP-complete problem in polynomial time. Therefore if a polynomial time solution for an NP-complete problem exists, the algorithm:

Have problem: 1) Transform problem into NP-complete problem (polynomial time) 2) Solve NP-complete problem (polynomial time)

Two polynomial time steps make a polynomial time algorithm.

The proof that every problem in NP is polynomial-time reducible to an NP-complete problem is pretty long and complicated, involving the formalism of Turing Machines, but it can be found in most textbooks on the theory of computation and I believe it is called the Cook-Levin Theorem (that proves the 3SAT is NP-complete, and then most other theorems show that 3SAT is reducible to them).

Re:P versus NP Explained by leibniz on Monday February 03, 2014 @02:51PM (#7172997)
but not every NP-hard problem is in NP
Re:P versus NP Explained by mjfl on Monday February 03, 2014 @08:03PM (#7174770)
this is true, see edit