Seems like a direct contradiction. Typo, or am I missing something?
Seems like a direct contradiction. Typo, or am I missing something?
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.
The error is that not all problems in NP are "extremely difficult for computers to solve". The difficulty of solving problems in NP varies drastically between particular problems.
> P problems are easy for computers to solve, and NP problems are easy for computers to check answers for.
The problem is the text still uses "NP problems" and "NP complete problems" interchangeably, when it shouldn't. (The diagram at the top gets it right!)
It is a typo. It should say "but potentially extremely difficult for computers to solve."