Математики из Массачусетсткого Технологического Института и Университета Оттавы уточнили вычислительную сложность игры Super Mario Bros. — оказалось, что игра является PSPACE-полной. Это означает, что для проверки того, проходима ли теоретически обобщенная игра, требуется полиномиальное количество памяти. Ранее ученые смогли показать, что по сложности игры по меньшей мере сопоставима с самой сложной задачей в классе NP (требующем для проверки решения «да/нет» полиномиального времени), входящем в состав PSPACE. Ключевым в доказательстве стало создание так называемых «дверей» — ситуаций, в которых определенные траектории могут менять «проходимость». О работе ученые доложат на Восьмой Международной конференции Fun with Algorithms (препринт статьи), кратко с результатами можно ознакомиться в пресс-релизе MIT.