Исследователи из Массачусетского технологического института, университета Оттавы и колледжа Барда в Саймонс Рок присвоили наивысший уровень сложности компьютерной игре Super Mario Brothers, пишет портал Innovanews. 

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

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