Геймерское
Оригинал взят у malaya_zemlya в Геймерское
Математик Джованни Вильетта доказал серию полезных теорем о сложности компьютерных игр. Складывается впечатление, что для настоящего раздражения центров удовольствия желательна минимум NP-сложность. Deflektor и Mindbender, принадлежащие P, только подтверждают правило, потому что - ну кто их помнит?
ИграПроизводительВычислительная сложностьBoulder DashFirst Star Software, 1984NP-сложнаяDeflektorVortex Software, 1987принадлежит LDoomid Software, 1993PSPACE-сложнаяLemmingsDMA Design, 1991NP-сложнаяLode RunnerBroderbund, 1983NP-сложнаяMindbenderMagic Bytes, 1989NL-сложнаяPac-ManNamco, 1980NP-сложнаяPipe ManiaThe Assembly Line, 1989NP-полнаяPrince of PersiaBroderbund, 1989PSPACE-сложнаяPuzzle Bobble 3Taito, 1996NP-полнаяSkweekLoriciel, 1989NP-полнаяStarcraftBlizzard Entertainment, 1998NP-сложнаяTronBally Midway, 1982NP-сложная
Ранее уже было доказано, что Тетрис - NP-полная игра, а Sokoban - PSPACE-полная
ЗЫ: Смотри также Computation Complexity of Games and Puzzles
posted on dreamwidth [
comments]