NP-Completeness
This video presents the same text shown beside it, spoken and on screen. It adds nothing the text does not say.
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.