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.
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.