Computer Science / Unit 3 CS 0163 short lesson, about 20 seconds
"NP Means Not Polynomial"
Captions available
The idea
NP does not mean "not P" — every problem in P is also in NP, because a deterministic solution needs no help from nondeterminism, so the two classes nest rather than oppose.
In practice
Shortest paths sits comfortably in both classes at once.
Where people slip
The N stands for nondeterministic, and for nothing else.
Your place on the trail
Every lesson rests on earlier ones and opens later ones. Tap any to jump.
Builds on
Unlocks
Something wrong in this lesson? Flag it · Sources for Computer Science