Игре Super Mario Brothers присвоили наивысший уровень сложности

Пройти игру Super Mario Brothers — это вам не ручей вброд перейти. Очень непростая затея, очень.

Вы удивитесь, но это не мнение подростков-геймеров — к такому выводу пришли исследователи из Массачусетского технологического института, университета Оттавы и колледжа Барда в Саймонс Рок.

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

И вот теперь выяснилось, что степень сложности уровня в игре даже выше, чем N, и относится к классу PSPACE.

В стандартной игре Super Mario Brothers водопроводчик Марио бежит по пересеченной местности, прибывающей с правой стороны. Компьютерный персонаж сражается с монстрами и выполняет различные задания, преодолевая кирпичные структуры, которые как стоят на земле, так и зависают в воздухе. Завершается уровень, когда Марио достигает флагштока.

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

— PSPACE — это наше заключительное слово, заявил профессор Эрик Димэйн.