Computer Science / Unit 3 CS 0162 short lesson, about 20 seconds
The Class NP
Captions available
The idea
The nondeterministic polynomial class, NP, holds every problem solvable in polynomial time by a nondeterministic algorithm — a machine free to explore all choices at once, succeeding if any path succeeds.
In practice
A puzzle cracked by trying every move simultaneously is the class's thought experiment.
Where people slip
No such machine exists; the class is definition, not hardware.
Your place on the trail
Every lesson rests on earlier ones and opens later ones. Tap any to jump.
Builds on
Something wrong in this lesson? Flag it · Sources for Computer Science