Mario is NP-Hard 🎮 Join the Newbie Nexus!

😺 Join the Newbie Nexus on Discord: https://discord.gg/CkWXnH9utV
⭐ Support on Patreon: https://patreon.com/NewbieIndieGameDev
👾 Play some of my games: https://newbie-indie-game-dev.itch.io/

Can Mario reach the flag? What begins as a simple question turns out to be logically equivalent to solving some of the hardest problems in science, engineering, logistics, finance, biology, and more. I explore the surprising connection between Super Mario Bros. and one of the biggest open problems in computer science: P vs NP. I break down how a game from the 80s leads us into the heart of computational complexity, and why answering this question could quite literally change the world.

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

0:00​ The Problem
0:59​ Complexity Classes
3:06​ P vs NP
3:59​ Super Mario Bros. is NP-hard
4:49​ 3SAT
6:16​ Proof: Expressions to Levels
8:56 Final Thoughts

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

🎥 Video by:

Nati Mendez
https://www.behance.net/natimendez
hello.natimendez@gmail.com

▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬

📚 Related reads:

Classic Nintendo Games are (Computationally) Hard - Greg Aloupis et al.
https://arxiv.org/pdf/1203.1895
Gaming is a hard job, but someone has to do it! - Giovanni Viglietta
https://m.giovanniviglietta.com/papers/gaming.pdf
A Framework for Proving the Computational Intractability of Motion Planning Problems - Jayson Lynch
https://erikdemaine.org/theses/jlynch.pdf
Complexity of Games
https://www.isnphard.com/

🎬 Related videos:

https://youtu.be/YX40hbAHx3s?si=Xq_--kA_WG8v9GQg
https://youtube.com/playlist?list=PLUl4u3cNGP63d33STUUBfZUpzFCVR5-PV&si=1JTSd0tV-Y4tG1e-
https://youtu.be/oS8m9fSk-Wk?si=GT1ehPGxIqQlTPPV
https://youtu.be/ycPDDnQh2qE?si=Hw7eJYpn_59-QXML
https://youtu.be/kTJ6HbZ6rEY?si=6yEvNaJNLtwnKW4a

#SuperMarioBros #ComputerScience #VideoGames #PvsNP