✖


Jump to content

Сложность игры

Комбинаторная теория игр измеряет сложность игры несколькими способами:

  1. Сложность пространства состояний (количество допустимых игровых позиций из начальной позиции),
  2. Размер дерева игр (общее количество возможных игр),
  3. Сложность решения (количество конечных узлов в наименьшем дереве решений для начальной позиции),
  4. Сложность игрового дерева (количество конечных узлов в наименьшем полноразмерном дереве решений для начальной позиции),
  5. Вычислительная сложность (асимптотическая сложность игры, когда она становится сколь угодно большой).

Эти меры включают понимание игровых позиций, возможных результатов и вычислений, необходимых для различных игровых сценариев.

Меры сложности игры

[ редактировать ]

Сложность пространства состояний

[ редактировать ]

— Сложность игры в пространстве состояний это количество допустимых игровых позиций, достижимых из начальной позиции игры. [1]

Когда это слишком сложно вычислить, верхнюю границу часто можно вычислить, также подсчитав (некоторые) нелегальные позиции, то есть позиции, которые никогда не могут возникнуть в ходе игры.

Размер дерева игры

[ редактировать ]

Размер дерева игры — это общее количество возможных игр, в которые можно играть: количество конечных узлов в дереве игры, корнем которых является начальная позиция игры.

Дерево игры обычно намного больше, чем пространство состояний, поскольку одни и те же позиции могут возникать во многих играх, делая ходы в разном порядке (например, в игре в крестики-нолики с двумя X и одним О на доске это позиция могла быть достигнута двумя разными способами в зависимости от того, где был помещен первый X). Верхнюю границу размера игрового дерева иногда можно вычислить, упрощая игру таким образом, чтобы только увеличивать размер игрового дерева (например, разрешая незаконные ходы), пока оно не станет управляемым.

Для игр, где количество ходов не ограничено (например, размером доски или правилом повторения позиций), дерево игры обычно бесконечно.

Деревья решений

[ редактировать ]

Следующие два измерения используют идею дерева решений , которое является поддеревом игрового дерева, где каждая позиция помечена словами «игрок А выигрывает», «игрок Б выигрывает» или «ничья», если можно доказать, что эта позиция имеет это значение (при условии лучшей игры обеих сторон) путем изучения только других позиций на графике. (Терминальные позиции могут быть помечены напрямую; позиция, в которой игрок А должен двигаться, может быть помечена как «победа игрока А», если любая последующая позиция является победой для игрока А, или помечена как «победа игрока Б», если все последующие позиции являются победами для игрока Б, или помечается как «ничья», если все последующие позиции либо ничейны, либо выигрывают для B. И, соответственно, для позиций с B для перемещения.)

Сложность решения

[ редактировать ]

Сложность принятия решения в игре — это количество конечных узлов в наименьшем дереве решений, которое устанавливает значение начальной позиции.

Сложность игрового дерева

[ редактировать ]

Сложность игрового дерева игры — это количество конечных узлов в наименьшем дереве решений полной ширины , которое устанавливает значение начальной позиции. [1] Дерево полной ширины включает все узлы на каждой глубине.

Это оценка количества позиций, которые необходимо оценить при минимаксном поиске, чтобы определить значение начальной позиции.

Трудно даже оценить сложность дерева игры, но для некоторых игр приближение можно дать, возведя средний коэффициент ветвления игры b в степень числа ходов d в средней игре, или:

.

Вычислительная сложность

[ редактировать ]

Вычислительная сложность игры описывает асимптотическую сложность игры по мере того, как она становится сколь угодно большой, выражается через обозначение большого О или как принадлежность к классу сложности . Эта концепция не применима к конкретным играм, а скорее к играм, которые были обобщены, поэтому их можно сделать сколь угодно большими, обычно играя в них на доске размером n × n . (С точки зрения вычислительной сложности игра на доске фиксированного размера представляет собой конечную задачу, которую можно решить за O(1), например, с помощью таблицы поиска позиций до лучшего хода в каждой позиции.)

Асимптотическая сложность определяется наиболее эффективным (с точки зрения рассматриваемого вычислительного ресурса ) алгоритмом решения игры; наиболее распространенная мера сложности ( время вычисления ) всегда ограничена снизу логарифмом асимптотической сложности пространства состояний, поскольку алгоритм решения должен работать для каждого возможного состояния игры. Верхний предел будет ограничен сложностью любого конкретного алгоритма, который работает для семейства игр. Аналогичные замечания относятся и ко второй наиболее часто используемой мере сложности — объему пространства или компьютерной памяти, используемому для вычислений. Неочевидно, что существует какая-либо нижняя граница пространственной сложности для типичной игры, поскольку алгоритму не требуется хранить состояния игры; однако известно, что многие представляющие интерес игры являются PSPACE-сложными , и из этого следует, что их пространственная сложность также будет ограничена снизу логарифмом асимптотической сложности пространства состояний (технически оценка представляет собой только полином от этой величины; но обычно известно, что он линейный).

  • Минимаксная «сначала в глубину» стратегия будет использовать время вычислений , пропорциональное сложности дерева игры, поскольку оно должно исследовать все дерево, и объем памяти, полиномиальный в логарифме сложности дерева, поскольку алгоритм должен всегда хранить один узел дерева. дерево на каждой возможной глубине перемещения, а количество узлов на самой высокой глубине перемещения и есть сложность дерева.
  • Обратная индукция будет использовать как память, так и время, пропорциональные сложности пространства состояний, поскольку она должна вычислить и записать правильный ход для каждой возможной позиции.

Пример: крестики-нолики (крестики-нолики).

[ редактировать ]

Для крестиков-ноликов простая верхняя граница размера пространства состояний равна 3 9 = 19 683. (Для каждой клетки есть три состояния и девять ячеек.) В этот подсчет входит множество незаконных позиций, например позиция с пятью крестиками и без нулей или позиция, в которой у обоих игроков есть ряд из трех. Более тщательный подсчет, исключающий эти нелегальные позиции, дает 5478. [2] [3] А если считать вращения и отражения позиций одинаковыми, то получается всего 765 существенно различных позиций.

Чтобы связать дерево игры, существует 9 возможных начальных ходов, 8 возможных ответов и т. д., так что их максимум 9! или всего 362 880 игр. Однако для решения игры может потребоваться менее 9 ходов, а точное подсчет дает 255 168 возможных игр. Если считать вращения и отражения позиций одинаковыми, то возможных игр всего 26 830.

Вычислительная сложность игры «крестики-нолики» зависит от того, как она обобщается . Естественным обобщением является m , n , k -игры : игра ведется на доске m x n , причем победителем становится первый игрок, получивший k подряд. Сразу понятно, что эту игру можно решить в DSPACE ( mn ), пройдя по всему дереву игры. Это помещает его в важный класс сложности PSPACE . После некоторой дополнительной работы можно показать, что он PSPACE-полный . [4]

Сложности некоторых известных игр

[ редактировать ]

Из-за большого размера игровых сложностей в этой таблице приведен потолок их логарифма по основанию 10. (Другими словами, количество цифр). Ко всем следующим числам следует относиться с осторожностью: кажущиеся незначительными изменения в правилах игры могут изменить цифры (которые в любом случае часто являются приблизительными оценками) на огромные факторы, которые легко могут быть намного больше, чем показанные цифры.

Примечание: упорядочено по размеру дерева игры.

Игра Размер платы

(позиции)

Сложность пространства состояний

(как журнал по основанию 10)

Сложность игрового дерева

(как журнал по основанию 10)

Средняя продолжительность игры

( слои )

Фактор разветвления Ссылка Класс сложности подходящей обобщенной игры
Крестики-нолики 9 3 5 9 4 PSPACE-полный [5]
Да 15 3 8 14 3.7 PSPACE-полный [6]
Пентамино 64 12 18 10 75 [7] [8] ?, но в PSPACE
Потерянный [9] 14 13 18 50 [7] Обобщение неясно
Соедините четыре 42 13 21 36 4 [1] [10] ?, но в PSPACE
Властный (8 × 8) 64 15 27 30 8 [7] ?, но в PSPACE ; в P для определенных размеров [11]
Высокомерный 14 15 33 [7]
Английские шашки (8х8) (шашки) 32 20 или 18 40 70 2.8 [1] [12] [13] EXPTIME-завершено [14]
Открытие [15] 12 12 32 60 3.5 [1] Обобщение неясно
Кубик 64 30 34 20 54.2 [1] PSPACE-полный [5]
Двойной фиктивный мост [номер 1] (52) <17 <40 52 5.6 PSPACE-полный [16]
Обрезание 45 21 46 44 11 [17] ?, но в EXPTIME
Девять мужских Моррисов 24 10 50 50 10 [1] ?, но в EXPTIME
Таблут 81 27 [18]
Международные шашки (10х10) 50 30 54 90 4 [1] EXPTIME-завершено [14]
Китайские шашки (2 комплекта) 121 23 180 [19] EXPTIME - завершено [20]
Китайские шашки (6 комплектов) 121 78 600 [19] EXPTIME - завершено [20]
Возвращенный (Отелло) 64 28 58 58 10 [1] PSPACE-полный [21]
OnTop (базовая игра для 2 игроков) 72 88 62 31 23.77 [22]
Направления действий 64 23 64 44 29 [23] ?, но в EXPTIME
Гомоку (15х15, вольный стиль) 225 105 70 30 210 [1] PSPACE-полный [5]
Шестигранник (11x11) 121 57 98 50 96 [7] PSPACE-полный [5]
шахматы 64 44 123 70 35 [24] EXPTIME-полный (без правила розыгрыша в 50 ходов ) [25]
Bejeweled и Candy Crush (8x8) 64 <50 70 [26] NP-жесткий
ГИФП 37 25 132 90 29.3 [27]
Подключить6 361 172 140 30 46000 [28] PSPACE-полный [29]
Нарды 28 20 144 55 250 [30] Обобщение неясно
Сянци 90 40 150 95 38 [1] [31] [32] ?, считается, что EXPTIME-полный
Морское ушко 61 25 154 87 60 [33] [34] PSPACE-hard и в EXPTIME
Гаванна 271 127 157 66 240 [7] [35] PSPACE-полный [36]
Твикст 572 140 159 60 452 [37]
Высокий 90 44 160 100 40 [32] ?, считается, что EXPTIME-полный
Коридор 81 42 162 91 60 [38] ?, но в PSPACE
Каркассон (базовая игра для 2 игроков) 72 >40 195 71 55 [39] Обобщение неясно
Амазонки (10х10) 100 40 212 84 374 или 299 [40] [41] [42] PSPACE-полный [43]
Сёги 81 71 226 115 92 [31] [44] EXPTIME-завершено [45]
Турн и Таксис (2 игрока) 33 66 240 56 879 [46]
Вперед (19x19) 361 170 360 150 250 [1] [47] [48] EXPTIME-полный (без правила суперко ) [49]
Аримаа 64 43 402 92 17281 [50] [51] [52] ?, но в EXPTIME
Стратег 92 115 535 381 21.739 [53]
Бесконечные шахматы бесконечный бесконечный бесконечный бесконечный бесконечный [54] Неизвестно, но мат-в-n разрешима [55]
Магия: Сбор [56] АХ-жесткий [57]
Вордл 5 12,972 6 [58] NP-hard , неизвестно, завершен ли PSPACE с параметризацией.

Примечания

[ редактировать ]
  1. ^ Бридж с двойным манекеном (т. е. задачи с двойным манекеном в контексте контрактного бриджа ) не является настоящей настольной игрой, но имеет похожее дерево игры и изучается в компьютерном бридже . Можно считать, что таблица бриджа имеет один слот для каждого игрока и трюк для разыгрывания карты, что соответствует размеру доски 52. Сложность дерева игры - это очень слабая верхняя граница: 13! в пользу 4 игроков независимо от законности. Сложность пространства состояний рассчитана на одну конкретную сделку; то же самое независимо от законности, но с устранением многих транспозиций. Последние 4 слоя всегда являются вынужденными перемещениями с коэффициентом ветвления 1.

Ссылки

[ редактировать ]
  1. ^ Перейти обратно: а б с д и ж г час я дж к л Виктор Эллис (1994). В поисках решений в играх и искусственном интеллекте (PDF) (кандидатская диссертация). Университет Лимбурга, Маастрихт, Нидерланды. ISBN  90-900748-8-0 .
  2. ^ «Комбинаторика - Выбор пространства состояний крестиков-ноликов» . Математический обмен стеками . Проверено 8 апреля 2020 г.
  3. ^ Т, Брайан (20 октября 2018 г.). "Бцан/generate_tictactoe" . Гитхаб . Проверено 8 апреля 2020 г.
  4. ^ Стефан Райш (1980). «Гобанг является PSPACE-полным». Акта Информатика . 13 (1): 59–66. дои : 10.1007/bf00288536 . S2CID   21455572 .
  5. ^ Перейти обратно: а б с д Стефан Райш (1981). «Hex является PSPACE-полным». Акта Информ (15): 167–191.
  6. ^ Слани, Вольфганг (2000). «Сложность графовых игр Рэмзи». В Марсленде Т. Энтони; Фрэнк, Ян (ред.). Компьютеры и игры, Вторая международная конференция, CG 2000, Хамамацу, Япония, 26-28 октября 2000 г., Пересмотренные статьи . Конспекты лекций по информатике. Том. 2063. Спрингер. стр. 186–203. дои : 10.1007/3-540-45579-5_12 .
  7. ^ Перейти обратно: а б с д и ж Х.Дж. ван ден Херик; Вымирание JWHM; Дж. ван Рейсвейк (2002). «Игры решены: сейчас и в будущем» . Искусственный интеллект . 134 (1–2): 277–311. дои : 10.1016/S0004-3702(01)00152-7 .
  8. ^ Орман, Хилари К. (1996). «Пентомино: победа первого игрока» (PDF) . В Новаковски, Ричард Дж. (ред.). Игры без шансов: материалы семинара по комбинаторным играм, проходившего в Беркли, Калифорния, 11–21 июля 1994 г. Публикации НИИ математических наук. Том. 29. Издательство Кембриджского университета. стр. 339–344. ISBN  0-521-57411-0 . МР   1427975 .
  9. ^ Правила см. у ван ден Херика и др.
  10. ^ Джон Тромп (2010). «Игровая площадка John's Connect Four» .
  11. ^ Лахманн, Майкл; Мур, Кристофер; Рапапорт, Иван (2002). «Кто победит в Доминировании на прямоугольных досках?». В Новаковски, Ричард (ред.). Еще игры без шансов: материалы 2-го семинара по теории комбинаторных игр, проходившего в Беркли, Калифорния, 24–28 июля 2000 г. Публикации НИИ математических наук. Том. 42. Издательство Кембриджского университета. стр. 307–315. ISBN  0-521-80832-4 . МР   1973019 .
  12. ^ Джонатан Шеффер; и др. (6 июля 2007 г.). «Шашки решены» . Наука . 317 (5844): 1518–1522. Бибкод : 2007Sci...317.1518S . дои : 10.1126/science.1144079 . ПМИД   17641166 . S2CID   10274228 .
  13. ^ Шеффер, Джонатан (2007). «Игра окончена: черные играют и берут шашки» (PDF) . Журнал ICGA . 30 (4): 187–197. doi : 10.3233/ICG-2007-30402 . Архивировано из оригинала (PDF) 3 апреля 2016 г.
  14. ^ Перейти обратно: а б Дж. М. Робсон (1984). «N на N шашек завершено». SIAM Journal по вычислительной технике . 13 (2): 252–267. дои : 10.1137/0213018 .
  15. ^ Правила см. в Allis 1994.
  16. ^ Бонне, Эдуард; Джамейн, Флориан; Саффидин, Абдалла (2013). «О сложности взятия фокусов в карточных играх» . В Росси, Франческа (ред.). IJCAI 2013, Материалы 23-й Международной совместной конференции по искусственному интеллекту, Пекин, Китай, 3–9 августа 2013 г. IJCAI/AAAI. стр. 482–488.
  17. ^ MPD Шадд; МХМ Винандс; JWHM Уитервейк; Х.Дж. ван ден Херик; MHJ Бергсма (2008). «Лучшая игра в Фанороне приводит к ничьей» (PDF) . Новая математика и естественные вычисления . 4 (3): 369–387. дои : 10.1142/S1793005708001124 .
  18. ^ Андреа Галасси (2018). «Верхняя граница сложности таблута» .
  19. ^ Перейти обратно: а б Дж. И. Белл (2009). «Самая короткая игра в китайские шашки и связанные с ней задачи». Целые числа . 9 . arXiv : 0803.1245 . Бибкод : 2008arXiv0803.1245B . дои : 10.1515/INTEG.2009.003 . S2CID   17141575 .
  20. ^ Перейти обратно: а б Касаи, Такуми; Адачи, Акео; Ивата, Сигеки (1979). «Классы игр с камушками и полные задачи». SIAM Journal по вычислительной технике . 8 (4): 574–586. дои : 10.1137/0208046 . МР   0573848 . Доказывает полноту обобщения на произвольные графы.
  21. ^ Ивата, Сигэки; Касаи, Такуми (1994) . доска является PSPACE-полной» . Theoretical Computer Science . 123 (2): 329–340. doi : 10.1016/0304-3975(94)90131-7 . MR   1256205 .
  22. ^ Роберт Бриземайстер (2009). Анализ и реализация игры OnTop (PDF) (Диссертация). Маастрихтский университет, факультет инженерии знаний.
  23. ^ Марк Х. М. Винандс (2004). Информированный поиск в сложных играх (PDF) (кандидатская диссертация). Маастрихтский университет, Маастрихт, Нидерланды. ISBN  90-5278-429-9 .
  24. ^ Размер пространства состояний и дерева игры в шахматы были впервые оценены в Клод Шеннон (1950). «Программирование компьютера для игры в шахматы» (PDF) . Философский журнал . 41 (314). Архивировано из оригинала (PDF) 6 июля 2010 г. Шеннон дал оценку 10 43 и 10 120 соответственно меньше верхней границы в таблице, который подробно описан в числе Шеннона .
  25. ^ Френкель, Авиезри С .; Лихтенштейн, Дэвид (1981). «Расчет идеальной стратегии для шахматы требуют экспоненты времени в " . Журнал комбинаторной теории, серия A. 31 ( 2): 199–214. doi : 10.1016/0097-3165(81)90016-9 . MR   0629595 .
  26. ^ Гуала, Лучано; Леуччи, Стефано; Натале, Эмануэле (2014). «Bejeweled, Candy Crush и другие игры в жанре «три в ряд» (NP-) сложны». Конференция IEEE 2014 по вычислительному интеллекту и играм, CIG 2014, Дортмунд, Германия, 26–29 августа 2014 г. IEEE. стр. 1–8. arXiv : 1403.5830 . дои : 10.1109/CIG.2014.6932866 .
  27. ^ Дидерик Вентинк (2001). Анализ и реализация игры Gipf (PDF) (Диссертация). Маастрихтский университет.
  28. ^ Чан-Мин Сюй; Ма, ЗМ; Цзюнь-Цзе Тао; Синь-Хе Сюй (2009). «Улучшения поиска по номеру подтверждения в Connect6». 2009 Китайская конференция по контролю и принятию решений . п. 4525. дои : 10.1109/CCDC.2009.5191963 . ISBN  978-1-4244-2722-2 . S2CID   20960281 .
  29. ^ Се, Мин Юй; Цай, Ши-Чун (1 октября 2007 г.). «О справедливости и сложности обобщенных игр «к подряд» . Теоретическая информатика . 385 (1–3): 88–100. дои : 10.1016/j.tcs.2007.05.031 . Получено 12 апреля 2018 г. - через dl.acm.org.
  30. ^ Тезауро, Джеральд (1 мая 1992 г.). «Практические вопросы обучения временным разницам» . Машинное обучение . 8 (3–4): 257–277. дои : 10.1007/BF00992697 .
  31. ^ Перейти обратно: а б Ши-Джим Йен-младший-Чан Чен; Тай-Нин Ян; Шун-Чин Сюй (март 2004 г.). «Компьютерные китайские шахматы» (PDF) . Журнал Международной ассоциации компьютерных игр . 27 (1): 3–18. doi : 10.3233/ICG-2004-27102 . S2CID   10336286 . Архивировано из оригинала (PDF) 14 июня 2007 г.
  32. ^ Перейти обратно: а б Парк Донхви (2015). «Пространственно-государственная сложность корейских шахмат и китайских шахмат». arXiv : 1507.06401 [ math.GM ].
  33. ^ Хор, Паскаль. «Реализация компьютерного проигрывателя для морских ушек с использованием альфа-бета-поиска и поиска Монте-Карло» (PDF) . Кафедра инженерии знаний, Маастрихтский университет . Проверено 29 марта 2012 г.
  34. ^ Копчински, Джейкоб С. (2014). Настойчивые вычисления: теория сложности и игра «Ушко» (Диссертация). Ридский колледж.
  35. ^ Йостен, Б. «Создание игрового агента Гаванны» (PDF) . Проверено 29 марта 2012 г.
  36. ^ Э. Бонне; Ф. Джамейн; А. Саффидин (25 марта 2014 г.). «Havannah и TwixT являются PSPACE-полными». arXiv : 1403.6518 [ cs.CC ].
  37. ^ Кевин Моескер (2009). Txixt: Теория, анализ и реализация (PDF) (Диссертация). Факультет гуманитарных наук и наук Маастрихтского университета.
  38. ^ Лиза Гленденнинг (май 2005 г.). Освоение Коридора (PDF) . Информатика (бакалаврская диссертация). Университет Нью-Мексико . Архивировано из оригинала (PDF) 15 марта 2012 г.
  39. ^ Кэтлин Хейден (2009). Реализация компьютерного плеера для Каркассона (PDF) (Диссертация). Маастрихтский университет, факультет инженерии знаний.
  40. ^ Меньший коэффициент ветвления предназначен для второго игрока.
  41. ^ Клёцер, Жюльен; Иида, Хироюки; Бузи, Бруно (2007). «Подход Монте-Карло в амазонках» (PDF) . Семинар по компьютерным играм, Амстердам, Нидерланды, 15-17 июня 2007 г. стр. 185–192.
  42. ^ НПДМ Хенсгенс (2001). «Подход к игре амазонок, основанный на знаниях» (PDF) . Университет Маастрихта, Институт знаний и агентных технологий.
  43. ^ Р. А. Хирн (2 февраля 2005 г.). «Amazons полностью поддерживает PSPACE». arXiv : cs.CC/0502013 .
  44. ^ Хироюки Иида; Макото Сакута; Джефф Ролласон (январь 2002 г.). «Компьютерные сёги» . Искусственный интеллект . 134 (1–2): 121–144. дои : 10.1016/S0004-3702(01)00157-6 .
  45. ^ Х. Адачи; Х. Камекава; С. Ивата (1987). «Сёги на доске n × n завершаются за экспоненциальное время». Пер. IEICE . J70-D: 1843–1852.
  46. ^ ФК Шадд (2009). Методы поиска Монте-Карло в современной настольной игре «Турн и Таксис» (PDF) (Диссертация). Маастрихтский университет. Архивировано из оригинала (PDF) 14 января 2021 г.
  47. ^ Джон Тромп; Гуннар Фарнебек (2007). «Комбинаторика Го» . В этой статье выводятся границы 48<log(log( N ))<171 числа возможных игр N .
  48. ^ Джон Тромп (2016). «Количество легальных позиций Го» .
  49. ^ Дж. М. Робсон (1983). «Сложность Го». обработка информации; Материалы Конгресса ИФИП . стр. 413–417.
  50. ^ Христос-Ян Кокс (2006). «Анализ и реализация игры Аримаа» (PDF) .
  51. ^ Дэвид Цзянь Ву (2011). «Рейтинг и оценка ходов в игре Аримаа» (PDF) .
  52. ^ Брайан Хаскин (2006). «Взгляд на фактор ветвления Аримаа» .
  53. ^ АФК Артс (2010). Соревновательная игра в Stratego (PDF) (Диссертация). Маастрихт.
  54. ^ CDA Эванс и Джоэл Дэвид Хэмкинс (2014). «Трансфинитные игровые значения в бесконечных шахматах». arXiv : 1302.4377 [ math.LO ].
  55. ^ Стефан Райш, Джоэл Дэвид Хэмкинс и Филипп Шлихт (2012). «Проблема мата в бесконечных шахматах разрешима». Конференция по вычислимости в Европе : 78–88. arXiv : 1201.5597 . {{cite journal}}: CS1 maint: несколько имен: список авторов ( ссылка )
  56. ^ Алекс Черчилль, Стелла Бидерман и Остин Херрик (2020). «Магия: Сбор завершен по Тьюрингу». arXiv : 1904.09828 [ cs.AI ]. {{cite arXiv}}: CS1 maint: несколько имен: список авторов ( ссылка )
  57. ^ Стелла Бидерман (2020). «Магия: Сбор так же сложен, как арифметика». arXiv : 2003.05119 [ cs.AI ].
  58. ^ Локштанов Даниил; Суберказо, Бернардо (14 мая 2022 г.). «Слово NP-сложно». arXiv : 2203.16713 [ cs.CC ].

См. также

[ редактировать ]
[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Game_complexity&oldid=1226841835"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 6d554b5e0d135197b67469347e09c86c__1717292760
URL1:https://arc.ask3.ru/arc/aa/6d/6c/6d554b5e0d135197b67469347e09c86c.html
Заголовок, (Title) документа по адресу, URL1:
Game complexity - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)