Skip to content
HomeVideos
AllLongsCategoriesPlaylists
BooksBlogsPodcasts
HistoryListsWatch laterLiked videosFollowing

The videos, books, blogs and podcasts Hacker News keeps recommending, all in one place.

VideosBooksBlogsPodcastsAboutPrivacySettings

Data from Hacker News, HackerTube, HackerBooks, HackerBlogs and Open Library. Credits · Not affiliated with Y Combinator.

HomeVideosBooksBlogsPodcasts
Ctrl K

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

    suckerpinch

    3 HN recommenders · recommended in 4 months, 2013–2021

    YouTube

    4:22 · 84K views · May 11, 2008

    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.

    Mathematics & Theoretical CSComputability & complexity theorySatire & parody
    1. 5:34
      On The Turing Completeness of PowerPoint (SIGBOVIK)Tom Wildenhain1.2M views • 9 years ago
    2. 10:44
      P vs. NP and the Computational Complexity Zoohackerdashery3.7M views • 12 years ago
    3. 42:36
      30 Weird Chess Algorithms: Elo Worldsuckerpinch965K views • 7 years ago
    4. 34:00
      Math's Fundamental FlawVeritasium31M views • 5 years ago
    5. 16:18
      Computer program that learns to play classic NES gamessuckerpinch2.2M views • 13 years ago
    6. 6:14
      Turing & The Halting Problem - ComputerphileComputerphile919K views • 12 years ago
    7. 5:58
      MarI/O - Machine Learning for Video GamesSethBling12M views • 11 years ago
    8. 13:14
      Did Nintendo really forget to Optimize Super Mario 64 ? | MVGModern Vintage Gamer1.3M views • 6 years ago
    9. 57:03
      HACKENBUSH: a window to a new world of mathOwen Maitzen562K views • 5 years ago
    10. 51:32
      Great Impractical Ideas in Computer Science: PowerPoint ProgrammingTom Wildenhain2.2M views • 7 years ago
    11. 17:58
      What P vs NP is actually aboutPolylog257K views • 2 years ago
    12. 22:54
      I Built a COMPUTER in Magic: The GatheringBecause Science2M views • 7 years ago
    13. 24:13
      Uppestcase and Lowestcase Letters [advances in derp learning]suckerpinch477K views • 5 years ago
    14. 22:21
      Reverse emulating the NES to give it SUPER POWERS!suckerpinch1.1M views • 8 years ago
    15. 19:08
      NaN Gates and Flip FLOPSsuckerpinch314K views • 7 years ago
    16. 26:41
      Finding the BEST sine function for Nintendo 64Kaze Emanuar418K views • 3 years ago
    17. 42:43
      "Propositions as Types" by Philip WadlerStrange Loop Conference144K views • 11 years ago
    18. 53:22
      Ruby Conf 12 - Y Not- Adventures in Functional Programming by Jim WeirichConfreaks66K views • 13 years ago
    19. 1:30
      Life in lifePhillip Bradbury4.1M views • 14 years ago
    20. 1:11
      Infinite Mario AI - Long LevelRobin Baumgarten1.3M views • 17 years ago

    4 comments from Hacker News

    1. @hotwireJun 2018· 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: this video

      Strongly recommendsView on HN
    2. @groovy2shoesMay 2013· 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] this video

      RecommendsView on HN
    3. @dane-pgpNov 2021· 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": this video

      RecommendsView on HN
    4. @ikeboyMay 2016· in “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)

      CitesView on HN