We think of Mario as an influential platforming game, but it also has interesting connections to complexity theory. In this video, we explore what makes Mario NPhard.
Twitter: / ubehavior
Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Zachary Greenberg
Music: Gravity Sound ( / @gravitysound )
—
References:
Paper: https://arxiv.org/abs/1203.1895
Reduction: https://en.wikipedia.org/wiki/Reducti...)
3SAT: https://en.wikipedia.org/wiki/Boolean...
P vs NP Playlist: • P vs NP