капибара
Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр. Статья ученого пока не принята к публикации, однако ее препринт доступен на сайте arXiv.org. читать дальше Как оказалось, большая часть игр принадлежит к так называемому классу NP - это задачи, решающиеся за полиномиальное время на недетерминированной машине Тьюринга (то есть машине, программа которой допускает развилки). Также нашлись игры, принадлежащие к классу P (полиномиальное время на детерминированной машине Тьюринга), L (задачи, решаемые с привлечение логарифмически зависящего от начальных данных количества памяти детерминированной машиной Тьюринга), NL (то же, что и L, только машина недетрминированная) и PSPACE. Кроме этого, несколько задач оказались NP-полными и PSPACE-полными. По сути это самые сложные задачи в своих классах - к ним за полиномиальное время можно свести любую задачу из данного класса. Например, к NP-полным задачам относится задача коммивояжера - поиск замкнутого кратчайшего пути в графе, который проходит по каждой вершине хотя бы один раз. Полный список результатов выглядит следующим образом: Boulder Dash (1984) - сложность NP Deflektor (1987) - сложность L Doom (1993) - сложность PSPACE Lemmings (1991) - сложность NP Lode Runner (1983) - сложность NP Mindbender (1989) - сложность NL Pac-Man (1980) - сложность NP Pipe Mania (1989) - NP-полная игра Prince of Persia (1989) - PSPACE-полная игра Puzzle Bobble 3 (1996) - NP-полная игра Skweek (1989) - NP-полная игра Starcraft (1998) - сложность NP Tron (1982) - сложность NP Вильетта также заявил, что аналогичный анализ для современных игр смысла не имеет, так как в них могут встречаться неразрешимые головоломки. |
|||
| http://lenta.ru/news/2012/01/30/npgames/ |
Какой молодец. Сразу видно, человек делом занят, а не в игрушки играется!