Understanding Why Mario Is NP-Hard Through Polynomial Reductions
This video explores the complexity behind the popular platformer Mario, explaining what makes it NP-hard through the concept of polynomial reductions in computational complexity theory.
Undefined Behavior
50.1K views • Jan 28, 2019
About this video
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-
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-
Tags and Topics
Browse our collection to discover more content in these categories.
Video Information
Views
50.1K
Likes
1.4K
Duration
10:53
Published
Jan 28, 2019
User Reviews
4.7
(10)