Итальянец посчитал сложность выигрыша в компьютерные игры

Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр. Статья ученого пока не принята к публикации, однако ее препринт доступен на сайте arXiv.org.
В рамках работы Вильетта оценивал…Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр. Статья ученого пока не принята к публикации, однако ее препринт доступен на сайте arXiv.org.
В рамках работы Вильетта оценивал сложность вычисления последовательности действий, который приводят к победе в игре. В первой части статьи итальянец приводит серию теорем, которые позволяют связать вычислительную сложность игры с наличием в ней некоторых конкретных элементов. К последним, например, относятся рычаги, которые надо нажать, чтобы открылась некоторая дверь, призы, которые необходимо собирать, и многое другое.
Как оказалось, большая часть игр принадлежит к так называемому классу NP — это задачи, решающиеся за полиномиальное время на недетерминированной машине Тьюринга (то есть машине, программа которой допускает развилки). Также нашлись игры, принадлежащие к классу P (полиномиальное время на детерминированной машине Тьюринга), L (задачи, решаемые с привлечение логарифмически зависящего от начальных данных количества памяти детерминированной машиной Тьюринга), NL (то же, что и L, только машина недетрминированная) и PSPACE.
Кроме этого, несколько задач оказались NP-полными и PSPACE-полными. По сути это самые сложные задачи в своих классах — к ним за полиномиальное время можно свести любую задачу из данного класса. Например, к NP-полным задачам относится задача коммивояжера — поиск замкнутого кратчайшего пути в графе, который проходит по каждой вершине хотя бы один раз.
Полный список результатов выглядит следующим образом:
Boulder Dash (1984) — сложность NPDeflektor (1987) — сложность LDoom (1993) — сложность PSPACELemmings (1991) — сложность NPLode Runner (1983) — сложность NPMindbender (1989) — сложность NLPac-Man (1980) — сложность NPPipe Mania (1989) — NP-полная играPrince of Persia (1989) — PSPACE-полная играPuzzle Bobble 3 (1996) — NP-полная играSkweek (1989) — NP-полная играStarcraft (1998) — сложность NPTron (1982) — сложность NP
Вильетта также заявил, что аналогичный анализ для современных игр смысла не имеет, так как в них могут встречаться неразрешимые головоломки.
Источник: