Proved that Super Mario is an NP-full challenge.

Analysis of the computational complexity of the five classic games for Nintendo showed that among them there are NP-complete problems, that is, which are solved in polynomial time on the so-called non-deterministic Turing machines. Simply put, these are mathematically very complicated tasks, comparable to the traveling salesman problem or the graph coloring problem.

Scientists analyzed the following games: Mario, Donkey Kong, Legend of Zelda, Metroid and Pokemon. As it turned out, the definition of NP-completeness applies to all games of the Mario and Donkey Kong series. Some games in other series belong to the NP class, and some games belong to the PSPACE class.

Of course, the commercial versions of Mario were specifically designed so that the levels could be completed, but as part of this study, the scientists changed the levels in order to reduce the game to the logical task of satisfying the Boolean formulas and to check whether all variables found in the formula can assign falsehood and truth so that the formula becomes true. The variables in this formula are opponents and bonuses on the playing field. If they allow you to complete a level, then the formula is true. If the level is impossible to pass, then there is a contradiction.
')
From a developer's point of view, NP-full games are difficult because initially there is no easy way to check if there is an opportunity to play the game to the end. On the other hand, such games will be very interesting for players, writes New Scientist .