3 ms·
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
by 14113 13y ago
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.
- _greim_ 13y agoAhh. Thank you. This actually makes more sense than the article itself!