Slashdot Mirror
Classic Nintendo Games Are NP-Hard
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."
Harder than Battletoads? I think not.
Skype is too convoluted... Now I'm reverse-engineering the Kyoto Protocol.
They were "Nintendo hard" long before anyone realized they were NP-hard, and that's a much more meaningful measure for difficulty of video games on a practical level.
Whether a problem is NP-hard has nothing to do with it being hard for you. NP is hard only for computers, because they are restricted to brute force search for the solution. As a human being, you use your intuition to probabalistically arrive at a likely solution instead of using a logical process to arrive at an exact and perfect solution. People do not care much about absolute knowledge, which is the province of science; we care about practical knowledge, which is the province of engineering. For example, the infamous travelling salesman problem is NP-hard, which makes it impossible for a computer to come up with the optimal solution in a predictable amount of time. However, in real life this has minimal utility because the difference between the optimal solution and the "good enough" solution that millions of travelling salesmen come up with every day is likely not financially significant. This is true in most everyday situations: we simply don't care if the solutions we use are the best available, only that they are the best we can think of in a reasonable amount of time.
This is not to say that we don't need the absolute knowledge that science provides; in many cases it does indeed lead to the practical knowledge that improves our lives. But because most absolute knowledge has no useful applications, it does make sense to have a lot fewer scientists than engineers.
Assuming the analysis is correct and these games are NP-hard, then what is interesting is not that some of us failed miserably at the games but so very many people did quite well. The human brain is a special-purpose computer that excels at solving problems critical to the species' survival. This suggests to me that reformulating problems of interest into a form that the brain can process (e.g., video games) might be an excellent way to tap the computational power of the brain. Wouldn't it be interesting if the millions of brains playing games were actually solving major problems in physics, biochemistry, etc.? Call it "crowd-sourced computation".
There's no sense in being precise when you don't even know what you're talking about. -- John von Neumann
No, NP-Hard cannot be, nor ever become, a buzz word, because NP-Hard has a clear, well-defined meaning. Buzzwords are defined by their own lack of definition, making them perfect for marketing and generally impressing people without saying anything meaningful.
You know, there is a difference between trolling and pointing out the flaws in your reasoning. Just saying.
For a gentler introduction, see P vs. NP.
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.
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!
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