Classic Nintendo Games Are NP Hard: "You may have have thought that games like Mario, Donkey Kong and so on were hard at the time you were playing them, but you probably didn't guess that they were NP-hard. NP-hard problems are in a sense the ones that are most difficult to solve by computational means because the time it takes to find a solution tends to increase so quickly with the size of the problem that it just isn't practical to perform the computation. Now we have some results from computer scientists at Universite Libre de Bruxelles and MIT Computer Science and Artificial Intelligence Laboratory (CSAIL) that many classic games contain within them an NP-hard problem. It is a bit like the discovery of a black hole at the center of every galaxy. Should either fact be surprising?"
No comments:
Post a Comment