News for hackers. Stuff that matters.
Re:P versus NP Explained by 14113 on Monday February 03, 2014 @02:08PM (#7172760)
Sort of - we don't know if NP problems are hard for computers to solve, that's really the whole question!

Technically, P is a subset of NP. Problems in NP have answers (called certificates) which can be verified, or checked, using an algorithm that runs in polynomial time (that is asymptotically O(n^x), where X is a finite integer). Problems that are in P are those that have a polynomial time algorithm to construct an answer.

Any problem that's in P is therefore in NP, as we can simply run the algorithm for constructing the answer then compare it with the certificate to see if they match.

P vs NP simply asks if all problems in NP can be solved in polynomial time, hence P=NP.

Re:P versus NP Explained by _greim_ on Monday February 03, 2014 @02:19PM (#7172821)
Ahh. Thank you. This actually makes more sense than the article itself!