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

Купить номер с этой статьей в PDF