Игра Super Mario признана NP-полной задачей
Математический анализ сложности пяти классических игр для Nintendo показал, что среди них есть NP-полные задачи, то есть которые решаются за полиномиальное время на так называемых недетерминированных машинах Тьюринга. Проще говоря, это математически очень сложные задачи, сравнимые с задачей коммивояжёра или проблемой раскраски графа.
Учёные проанализировали следующие игры: Mario, Donkey Kong, Legend of Zelda, Metroid и Pokemon. Как выяснилось, ко всем играм серий Mario и Donkey Kong применимо определение о NP-полноте. Кроме того, отдельные игры других серий принадлежат к классу NP, а некоторые игры из серии Zelda — к классу PSPACE.
Читать дальше →
Полный текст статьи читайте на Habrahabr.ru
