This lesson's interactive features are locked, please to keep using them
NP
Nondeterministic polynomial time, NP, is the set of problems whose solutions can be verified in polynomial time, but not necessarily solved in polynomial time.
P Is in NP
Because all problems that can be solved in polynomial time can also be verified in polynomial time, all the problems in P are also in NP.
The Oracle
A good way of thinking about problems in NP is to imagine that we have a magic oracle that gives us potential solutions to problems. Here would be our process for finding if a problem is in NP:
- Present the problem to the magic oracle
- The magic oracle gives us a potential solution
- We verify in polynomial time that the solution is correct
If we can do the verification in polynomial time, the problem is in NP, otherwise, it isn't.
Click to play video