Classic Nintendo Games Are NP-Hard 204
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."
Not just nintendo games (Score:4, Interesting)
My favorite NP-hard game is adom. Just try it - see my sig.
Comment removed (Score:2, Interesting)
pointless (Score:5, Interesting)
These games aren't "NP-hard" because they are fixed size and fixed levels. Complexity results show you nothing about the difficulty of individual instances.
What is "NP-hard" is some generalization of these games chosen by the authors, with a particular chosen outcome (e.g., maximum score). Whether that generalization is still a good game, or even the same game, is questionable.
No, you don't have an excuse (Score:5, Interesting)
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.
Human brains solve NP-Hard problems (Score:5, Interesting)
Infinite Mario (Score:4, Interesting)
I think it might all come down to how you look at the problem.
many people have programmed AI to beat Mario, I believe a few years ago their was some random Mario level generator (possibly called Infinite Mario) and a contest to create AI to play it. The simple act of taking it one frame at a time, dodging and jumping, is not hard to program AI or resource intensive I think, but any problem can be made complicated. If you are saying take a static level, how do you get the absolute maximum score, now of course that is NP hard.
Re:Not just nintendo games (Score:5, Interesting)
Re:Human brains solve NP-Hard problems (Score:5, Interesting)