Nondeterministic Super Mario Bros.

Nondeterministic Super Mario Bros. is the decision problem that takes a custom world map and levels of the NES Super Mario Bros. game as its input, and decides whether the player can rescue the princess.

The computational power of this decision problem is examined in the following article. (This wiki article summarizes a few highlights of that article.)

Erik D. Demaine, Giovanni Viglietta, and Aaron Williams, "Super Mario Bros. is Harder/Easier than We Thought", (2016), in Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016), http://erikdemaine.org/papers/Mario_FUN2016/

Since the original Super Mario Bros. runs on a computer with finite memory, the authors define a generalized version of the game that allows unbounded size state, but only in a very restricted way. In generalized Super Mario Bros., the world map can have any number of levels. The runtime state of the game tracks which levels are completed to the flagpole, and which levels are completed to at least the checkpoint. (Each level in this game may have a certain checkpoint location, and if Mario reaches that, then even if he dies, the next time he starts that level, he starts from the checkpoint instead of the start of the level.) The life counter of the player is also extended to an unbounded integer.

Other than the life counter, the mask of completed levels, and the mask of checkpointed levels, when the player is within a level, the state contains the level timer and the horizontal coordinate where the screen is scrolled. (Each level has a timeout, and if Mario has been in the level for longer than that, he dies.) Other than the parts listed, the rest of the state is finite: sprites and changes to the map are assumed to be remembered within the screen, which has a constant size, and the number of active sprites is limited to a constant as well.

Since the state of the game has a size that is bounded by a linear function of the input (world map and level description), it is clear that Nondeterministic Super Mario Bros. is in PSPACE. But whether it's easier to compute than that is a more difficult question, and at this point the article considers two different versions of generalized Super Mario Bros.

In the first generalized version of the game, defined in chapter 2 of the article, the input represents the map of each level explicitly. As a result, the screen scroll position is bounded by a linear function of the input size, and cannot track more information than a logarithmic function of the input size. The only parts of the state of the game that could grow too large are the timer, the level completion mask, and the level checkpoint mask, but the player's interaction with these is quite restricted. The authors prove that there is a polynomial time algorithm for Nondeterministic Super Mario Bros. in this version.

In the second generalized version, defined in chapter 3, levels may have a width that is exponential in the size of the input. The levels are described in such a way that each column of the map can be repeated any number of times, with the repetition count represented in binary in the input. The time limit for levels is also represented in binary and can be exponential. In this case, apart from the life counter and level timer, the screen position within the level can also grow to exponential in the size of the input, and can store a linear amount of data. The authors prove that the corresponding version of Nondeterministic Super Mario Bros. is NP-complete, so there is probably no polynomial time algorithm.