Mario is (NP-) Hard

😺 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