
 
 Helpful advice, for anyone looking to beat (or even play) Super Mario Brothers. (Jessica Rinaldi/Reuters) 
 
 The paper proves that five Nintendo classics are, in computer science terms, “NP-hard.” Those involve computing problems that, as Alex Armstrong of iProgrammer helpfully explains, “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.” 
 
 Classic Nintendo games, it turns out, fit the bill. Here’s the section on Super Mario Brothers, where the researchers note that there is a winning path, but it takes a really long time to find it: 
 
 Suppose there is a solution and consider any path that Mario takes through the stage. This path needs to visit every enemy at most once. The only other permanent objects in the game are potential Koopa shells, but these can only slide and fall, so they must either fall down a bottomless pit eventually and leave the game, or they enter a cycle where they bounce back and forth between two walls. In either case, the shell can be ignored, because a perfect player gains nothing by jumping on the shell to stop it. Therefore there exists a solution that is polynomial in the size of the input. 
 
 Not all Super Mario Brothers games, however, are created equal. The researchers find that Super Mario Brothers Lost Levels Edition (released only in Japan) does not fit the definition of “NP-Hard” because of — and this is verbatim from the paper — “Mario’s newfound ability to pick up Koopa shells.” 

 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? 
 
 Computer games often involve an element of search, and many NP-hard problem are about searching for a path or some arrangement of things that satisfies a condition. These are the sorts of things that get put in games to add a splash of logical difficulty to the physical skill of clicking buttons at the right time. Indeed, the clicking of the button at the right time is factored out of these proofs of complexity - these are results that apply to a perfect player with infinite speed and reaction times of zero. 
 
 The proofs are based on showing that the problem of deciding if a goal point is reachable from a starting point is NP-hard. The games are also generalized in that the size of the board is increased. 
 
 With these small changes it is proved that the following games are NP-hard: 
 
 Mario 
 
 Donkey Kong 
 
 Legend of Zelda 
 
 Metroid 
 
 Pokemon 
 
 The results apply to 
 
 Super Mario Bros. 1, 3, Lost Levels 
 
 Super Mario World 
 
 Donkey Kong Country 1.3 
 
 All Legend of Zelda games except Zelda II: The Adventure of Link 
 
 All Metroid games 
 
 All Pokemon role-playing games 
 
 So are all platform games NP-hard? 
 
 Almost certainly not, but are all "good" platform games NP-hard - a much more interesting problem. 
 
 More information 
 
 Further Reading 
 
 NP-Complete - Why so hard? 
 
 Physics Is NP Hard 
 
 Computational Complexity 
 
 Computability 
 
 Pancake flipping is hard - NP hard 
 
 Super Mario - Nintendo goes forward 
 
 Nintendo - the early history 
 
 
 
 
 
 
 
 Comments 
 
 
 
 Make a Comment or View Existing Comments Using Disqus 
 
 
 
 
 
 or email your comment to: comments@i-programmer.info 
 
 To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.
– Science has confirmed what you already knew as a 10-year-old: Super Mario Brothers is hard to beat. But the paper by a team of international computer scientists uses actual math to come to that pointy-headed conclusion, the Washington Post reports, and focuses on not just the Mario series but also Donkey Kong, Zelda, Metroid, and Pokemon. The title of the paper? "Classic Nintendo Games are (NP-)Hard." NP-Hard is a computer science term that Alex Armstrong explains on iProgrammer: "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." For example, the paper explains that it is possible to win Super Mario Brothers, it just takes a long time to figure out how. (But the paper explains that using terms like "polynomial" alongside terms like "Koopa shells.")