Mario is (NP-) Hard

An explanation of computational complexity and the P vs NP problem, proving why completing a level in Super Mario Bros. is NP-hard.

😺 Join the Newbie Nexus on Discord: discord.gg/CkWXnH9utV ⭐ Support on Patreon: patreon.com/NewbieIndieGameDev 👾 Play some of my games: 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 behance.net/natimendez hello.natimendez@gmail.com ▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬▬ 📚 Related reads: Classic Nintendo Games are (Computationally) Hard - Greg Aloupis et al. arxiv.org/pdf/1203.1895 Gaming is a hard job, but someone has to do it! - Giovanni Viglietta m.giovanniviglietta.com/papers/gaming.pdf A Framework for Proving the Computational Intractability of Motion Planning Problems - Jayson Lynch erikdemaine.org/theses/jlynch.pdf Complexity of Games isnphard.com/ 🎬 Related videos: youtu.be/YX40hbAHx3s?si=Xq_--kA_WG8v9GQg youtube.com/playlist?list=PLUl4u3cNGP63d33STUUBfZUpzFCVR5-PV… youtu.be/oS8m9fSk-Wk?si=GT1ehPGxIqQlTPPV youtu.be/ycPDDnQh2qE?si=Hw7eJYpn_59-QXML youtu.be/kTJ6HbZ6rEY?si=6yEvNaJNLtwnKW4a #SuperMarioBros #ComputerScience #VideoGames #PvsNP