Computer Science / Unit 3 CS 0164 short lesson, about 20 seconds
NP-Completeness
Captions available
The idea
NP-complete names the hardest problems in NP: a problem qualifies when it sits in NP and every NP problem reduces to it — one efficient solution would solve them all.
In practice
Longest path — the highest-cost route without repeats — is easy shortest path's hard twin.
Where people slip
No deterministic polynomial algorithm is known for any.
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