hotwireon Hacker News • Recommends
On “A general technique for automating NES games (2013)”
This guy is a genius and also freakin hilarious, I knew I recognised his voice from somewhere; watch this: link to this video
0:00 / 0:00
#np-complete#complexitytheory#supermariobros
SIGBOVIK 2007: Generalized Super Mario Bros. is NP-Complete
suckerpinch
202K subscribers • 15 videos on Hallway
- Recommended by 4 people: 3 on Hacker News and 1 in engineering communities.
- A classic. People kept recommending it from 2012 to 2021.
- Presented by Tom Murphy VII, computer scientist
- May be out of date. Uploaded 18 years ago, in an area where tools change fast.
Intermediate. Assumes working knowledge.
83K views18 years ago4 recommendations
Computer scienceGame developmentComputation and complexityAlgorithmsGame programming
Tom Murphy VII presents a satirical but mathematically sound proof that generalized Super Mario Bros. is NP-complete.
Presented by Vargomax V. Vargomax (via video) at SIGBOVIK 2007.Why it's here
4 people recommend thisWhat people say. Recommended as a hilarious and classic satirical presentation on computational complexity theory using retro video games.
groovy2shoeson Hacker News • Recommends
On “Classic Nintendo Games are NP-Hard”
Any time I see papers like this, I'm reminded of Vargomax V. Vargomax's classic SIGBOVIK 2007 paper 1. The presentation is also entertaining 2. 1 link 2 link to this video
dane-pgpon Hacker News • Recommends
On “Writing a Fuzzer for NES Games”
If we're sharing awesome Mario-related work by Tom Murphy, I have to include a link to his video "Generalized Super Mario Bros. is NP-Complete": link to this video
ikeboyon Hacker News • Mentions
On “TrackMania is NP-complete”
Similar examples: link link link link link link to this video link link link link link (Generated by going through HN search results for Turing complete and NP complete)
u/SolaTotaScripturain r/compsci • Mentions
On “Article of Mario NP-hardness?”
link to this video