StarCraft=Lemmings=PacMac
16:40 31.01.2012
Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр.
... <бла-бла-бла что-то умное от итальянца>
Полный список результатов выглядит следующим образом:
1 Boulder Dash (1984) - сложность NP
2Deflektor (1987) - сложность L
3Doom (1993) - сложность PSPACE
4Lemmings (1991) - сложность NP
5Lode Runner (1983) - сложность NP
6 Mindbender (1989) - сложность NL
7 Pac-Man (1980) - сложность NP
8 Pipe Mania (1989) - NP-полная игра
9 Prince of Persia (1989) - PSPACE-полная игра
10Puzzle Bobble 3 (1996) - NP-полная игра
11 Skweek (1989) - NP-полная игра
12 Starcraft (1998) - сложность NP
13 Tron (1982) - сложность NP
Источник

Я чесскать не понял ни жуя, но ведь среди Кузян есть честные информатики-математики с красными дипломами. Мож разрулите, что итальянец доказал-то? оО
Добавить комментарий:
Вы не зарегистрированы на сайте, поэтому данная функция отсутствует.
You are not registered on the site and this function is disabled.