SIGBOVIK 2007: Generalized Super Mario Bros. is NP-Complete
Why Hacker News recommends it
HN likes it as a funny, entertaining presentation, frequently linked in threads on NP-hardness of games and NES automation.
What it is
Tom Murphy's satirical SIGBOVIK 2007 presentation, delivered under a pseudonym, proving that generalized Super Mario Bros. is NP-complete. It is a short, deadpan take on a complexity theory result.
Recommended by 3 HN commenters across 3 different months, 2013 to 2021.
What Hacker News said
Strong rec hotwire · 2018-06 · 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: [this video]
Recommends groovy2shoes · 2013-05 · 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] [this video]
Recommends dane-pgp · 2021-11 · 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": [this video]
Cites ikeboy · 2016-05 · on “TrackMania is NP-complete”
Similar examples: [LINK] [LINK] [LINK] [LINK] [LINK] [this video] [LINK] [LINK] [LINK] [LINK] [LINK] (Generated by going through HN search results for Turing complete and NP complete)