Slashdot Mirror

← Back to Stories (view on slashdot.org)

Classic Nintendo Games Are NP-Hard

Posted by Soulskill on from the travelling-plumber-problem dept.

mikejuk writes "You may have have thought games like Super Mario Bros., Donkey Kong, and so on were hard at the time you were playing them, but you probably didn't guess they were NP-hard. Now we have some results from computer scientists at Universite Libre de Bruxelles and MIT Computer Science and Artificial Intelligence Laboratory that many classic games contain within them an NP-hard problem. It has been proven that the following game franchises are NP-hard (PDF): Mario, Donkey Kong, Legend of Zelda, Metroid and Pokemon. At least you now have an excuse for your low scores."

4 of 204 comments (clear)

  1. Re:Kid Icarus by kerohazel · · Score: 5, Funny

    Harder than Battletoads? I think not.

    --
    Skype is too convoluted... Now I'm reverse-engineering the Kyoto Protocol.
  2. Re:Kid Icarus by Anonymous Coward · · Score: 5, Funny

    There's a pretty big difference between "hard" and "fundamentally broken".

    Battletoads was hard because it was designed poorly.

    Sounds like SOMEONE'S still bitter they couldn't even beat the Turbo Tunnel.

  3. Re:Buzz by robthebloke · · Score: 5, Funny

    Where have you been for the last 5 weeks? Didn't you get the tweet? The term "NP-hard" has been superseded by "NP-cloud-based-social-media-hipster". Keep up!

  4. Re:Buzz by Chris+Burke · · Score: 5, Funny

    Where have you been for the last 5 weeks? Didn't you get the tweet? The term "NP-hard" has been superseded by "NP-cloud-based-social-media-hipster". Keep up!

    An "NP-cloud-based-social-media-hipster" would be proof that P=NP, since you're saying this cloud-based-social-media-hipster is in NP(Non-Pretentious), when it has already been proven that all hipsters are in P.

    --

    The enemies of Democracy are