u/RuloMurillo7in r/compsci • Recommends
On “Article of Mario NP-hardness?”
See link to this video
It is based on the paper you are looking for (see the comments).
0:00 / 0:00
#np-hardness#polynomialreduction#complexitytheory
What Makes Mario NP-Hard? (Polynomial Reductions)
Undefined Behavior
29K subscribers • 9 videos on Hallway
- Recommended by 2 people: 2 in engineering communities.
- Linked in the descriptionarXiv 1203.1895
- May be out of date. Uploaded 7 years ago, in an area where tools change fast.
Intermediate. Assumes working knowledge.
54K views7 years ago2 recommendations
Computer scienceGame developmentComputation and complexityAlgorithmsGame programming
An explanation of how polynomial reductions and 3-SAT are used to prove that Super Mario Bros. is NP-hard.
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: twitter.com/UBehavior Created by: Cory Chang Produced by: Vivian Liu Script Editor: Zachary Greenberg Music: Gravity Sound (youtube.com/channel/UCQ7Xmyu6eXpJfkEoMtRMv1w) — References: Paper: arxiv.org/abs/1203.1895 Reduction: en.wikipedia.org/wiki/Reduction_(complexity) 3-SAT: en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satis… P vs NP Playlist: youtube.com/playlist?list=PLlwsleWT767dnN25K_QgvdKkovK_t4K6-Why it's here
2 people recommend thisWhat people say. Recommended as a clear explanation of polynomial reductions and NP-hardness using Super Mario Bros. as an example.