Доказано, что игра Super Mario является NP-полной задачей
1 мин

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



В статье 
Так что друзья решили заняться другими проектами: один пошёл на работу в EFF, а второй ушёл во фриланс как дизайнер. Чтобы окончательно порвать с прошлым, они отдают двухлетнюю работу в общественное достояние, под лицензией GNU GPL. Наверное, это решение было принято не без влияния того, который ушёл в EFF.



Три дня назад на Хабре была опубликована статья