HackerTube

SIGBOVIK 2007: Generalized Super Mario Bros. is NP-Complete

suckerpinch3 HN recommenders · 2013–2021
84K views · comedy · evergreen · Uploaded 2008-05-11

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.

HN likes it as a funny, entertaining presentation, frequently linked in threads on NP-hardness of games and NES automation.

Computability & complexity theorySatire & parody

Watch on YouTube

4 comments from Hacker News

@groovy2shoes2013 · in “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] [VIDEO]

RecommendsView on HN
@ikeboy2016 · in “TrackMania is NP-complete”

Similar examples: [LINK] [LINK] [LINK] [LINK] [LINK] [VIDEO] [LINK] [LINK] [LINK] [LINK] [LINK] (Generated by going through HN search results for Turing complete and NP complete)

CitesView on HN
@hotwire2018 · in “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: [VIDEO]

Strongly recommendsView on HN
@dane-pgp2021 · in “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": [VIDEO]

RecommendsView on HN