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 NP-hard.

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...)
3-SAT: https://en.wikipedia.org/wiki/Boolean...
P vs NP Playlist:    • P vs NP