Исследователи не делали попытки доказать, что какие-то уровни коммерческих версий Super Mario имеют сложность PSPACE, но показали, что возможно составить уровень такой сложности, пользуясь стандартными элементами мира «Супер Марио». До этого те же ученые показали, что игра как минимум не менее сложна, чем самые сложные задачи класса NP, но затем вопрос сложности Super Mario Bros решено было выяснить окончательно.
К классу NP относятся задачи, чьи решения можно проверить за полиномиальное время (пропорциональное обозначаемому буквой N числу элементов данных, которые нужно обработать), притом что на поиск решения может уйти экспоненциальное время (пропорциональное 2N). Пример — чтобы разложить тысячезначное число на множители, не хватит мощности всех компьютеров мира и всего времени существования Вселенной, а проверить решение — перемножить множители — можно даже на смартфоне.
К PSPACE тоже относятся задачи, на решение которых нужно экспоненциальное время. Но у самых сложных задач этого класса экспоненциальное время требуется и для проверки решения.