|
Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр. Статья ученого пока не принята к публикации, однако ее препринт доступен на сайте 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
Вильетта также заявил, что аналогичный анализ для современных игр смысла не имеет, так как в них могут встречаться неразрешимые головоломки.
По материалам lenta.ru
Другие новости по теме
•
Звезде "Универа" воры вернули iPhone 4 с ее тайнами, украденный на съемках…
• Бывшего прокурора посадили за мошенничество на 9 миллионов…
•
В Афганистане 22-летнюю роженицу задушили ее муж со свекровью, недовольные рождением третьей дочери…
•
На москвича, выбросившего в форточку собаку пенсионерки, завели уголовное дело…
•
В Киргизии жители поселка выгнали таджиков после убийства кассирши в банке…
• В Петербурге у ФСБ украли 19 тонн латексных перчаток…
• В Приморье матроса посадили из-за суицида сослуживца…
•
Москвич получил пожизненный срок за убийства 15 женщин и ребенка: неуловимость маньяка списали на его обаятельность…
•
В Канаде вынесен вердикт бизнесмену-многоженцу, убившему трех дочерей и одну супругу за "честь семьи"…
•
В мексиканской тюрьме члены наркокартелей устроили резню: четверо убитых, 7 человек ранены…
• В Подмосковье капитана яхты посадили за гибель женщины…
• В Москве дали пожизненный срок убийце 16 человек…
• Сержанту дали 2,5 года за отбитую селезенку у солдата…
• СК закрыл дело о ложном доносе сына префекта…
• Руководитель госпредприятия попытался продать свою должность за 45 миллионов…
• В Пермском крае сожгли редакцию газеты…
| |
|
