Computer Science / CS 0164 · Atom · ~20 seconds
NP-Completeness
Video not yet published
to the StudyWalks catalog
to the StudyWalks catalog
State
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.
Show
Longest path — the highest-cost route without repeats — is easy shortest path's hard twin.
Watch for
No deterministic polynomial algorithm is known for any.