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.”