Ученые МТИ и еще ряда университетов показали, что поиск способа прохождения уровня классического платформера Super Mario Bros. относится к самым трудным задачам класса сложности PSPACE. Это значит, что она сложнее знаменитой «задачи коммивояжера» и задачи разложения на множители больших чисел — та и другая относятся к классу NP-полных, стоящего в иерархии ниже PSPACE.

Исследователи не делали попытки доказать, что какие-то уровни коммерческих версий Super Mario имеют сложность PSPACE, но показали, что возможно составить уровень такой сложности, пользуясь стандартными элементами мира «Супер Марио». До этого те же ученые показали, что игра как минимум не менее сложна, чем самые сложные задачи класса NP, но затем вопрос сложности Super Mario Bros решено было выяснить окончательно.

К классу NP относятся задачи, чьи решения можно проверить за полиномиальное время (пропорциональное обозначаемому буквой N числу элементов данных, которые нужно обработать), притом что на поиск решения может уйти экспоненциальное время (пропорциональное 2N). Пример — чтобы разложить тысячезначное число на множители, не хватит мощности всех компьютеров мира и всего времени существования Вселенной, а проверить решение — перемножить множители — можно даже на смартфоне.

К PSPACE тоже относятся задачи, на решение которых нужно экспоненциальное время. Но у самых сложных задач этого класса экспоненциальное время требуется и для проверки решения.