What Makes Mario NP-Hard? (Polynomial Reductions)

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: https://twitter.com/UBehavior

Created by: Cory Chang
Produced by: Vivian Liu
Script Editor: Zachary Greenberg
Music: Gravity Sound (https://www.youtube.com/channel/UCQ7Xmyu6eXpJfkEoMtRMv1w)

—

References:
Paper: https://arxiv.org/abs/1203.1895
Reduction: https://en.wikipedia.org/wiki/Reduction_(complexity)
3-SAT: https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability
P vs NP Playlist: https://www.youtube.com/playlist?list=PLlwsleWT767dnN25K_QgvdKkovK_t4K6-

Видео What Makes Mario NP-Hard? (Polynomial Reductions) канала Undefined Behavior