Список PSPACE-полных проблем

Вот некоторые из наиболее широко известных задач, которые являются PSPACE-полными, если их выразить как проблемы решения . Этот список ни в коей мере не является исчерпывающим.

Игры и головоломки

Обобщенные версии:

Амазонки ^[1]
Атомикс ^[2]
Шашки, если ничья форсирована после полиномиального числа ходов без прыжка ^[3]
Игра «Телескоп Дайсона» ^[4]
Перекрестные цели ^[5]
География
Версия игры Instant Insanity для двух игроков
Ко -фри Го ^[6]
Захват лестницы в Go ^[7]
Гомоку ^[8]
Шестигранник ^[9]
Конан ^[5]
Лемминги ^[10]
Узел Кейлс ^[11]
Посет-игра ^[12]
я вернулся ^[13]
Переправа через реку ^[14]
Час пик ^[14]
Как найти оптимальную игру в пасьянсе Маджонг ^[15]
Эрудит ^[16]
Сокобан ^[14]
Супер Братья Марио. ^[17]
Игра Черный камешек ^[18]
Игра Черно-белый камешек ^[19]
Ациклическая игра с камушками ^[20]
для одного игрока Игра с камушками ^[20]
Токен на ациклические игры с ориентированным графом: ^[11]

Логика

Количественные логические формулы
первого Логика равенства порядка ^[21]
Доказуемость в интуиционистской логике высказываний
Удовлетворение модальной логикой S4 ^[21]
первого порядка Теория натуральных чисел при операции-преемнике ^[21]
первого порядка Теория натуральных чисел стандартного порядка ^[21]
Теория первого порядка целых чисел стандартного порядка ^[21]
Теория первого порядка вполне упорядоченных множеств ^[21]
Теория первого порядка двоичных строк при лексикографическом упорядочении ^[21]
Теория первого порядка конечной булевой алгебры ^[21]
Стохастическая выполнимость ^[22]
Выполнимость линейной темпоральной логики и проверка модели ^[23]

Лямбда-исчисление

Проблема обитания типов для просто типизированного лямбда-исчисления

Автоматы и теория языка

Теория цепей

схемы Целочисленная оценка ^[24]

Теория автоматов

Словесная задача для линейных ограниченных автоматов ^[25]
Словесная задача для автоматов квазиреального времени ^[26]
Проблема пустоты для недетерминированного двустороннего конечного автомата ^[27]^[28]
Проблема эквивалентности недетерминированных конечных автоматов ^[29]^[30]
Проблема слов и проблема пустоты для нестирающих стековых автоматов ^[31]
Пустота пересечения неограниченного числа детерминированных конечных автоматов ^[32]
Обобщенная версия муравья Лэнгтона. ^[33]
Минимизация недетерминированных конечных автоматов ^[34]

Формальные языки

Проблема со словами для контекстно-зависимого языка ^[35]
Пустота пересечения для неограниченного числа регулярных языков. ^[32]
Регулярное выражение ^[36]
Проблема эквивалентности регулярных выражений ^[21]
Проблема пустоты для регулярных выражений с пересечением. ^[21]
Проблема эквивалентности без звездочек регулярных выражений с возведением в квадрат. ^[21]
Покрытие линейных грамматик ^[37]
Структурная эквивалентность линейных грамматик ^[38]
Проблема эквивалентности регулярных грамматик ^[39]
Проблема пустоты для ET0L грамматик ^[40]
Проблема со словами для ET0L грамматик ^[41]
Проблема принадлежности языка преобразователей деревьев для преобразователей деревьев с конечными состояниями сверху вниз ^[42]

Теория графов

краткие версии многих задач с графами, где графы представлены в виде логических схем, ^[43] упорядоченные двоичные диаграммы решений ^[44] или другие связанные представления:
- Первая проблема достижимости кратких графов. По сути, это то же самое, что и простейшая проблема существования плана в автоматизированном планировании и составлении графиков .
- планарность кратких графиков
- ацикличность кратких графов
- связность кратких графов
- существование эйлеровых путей в сжатом графе
Ограниченная логика ограничений для двух игроков ^[11]
Проблема канадского путешественника . ^[45]
Определение того, придут ли маршруты, выбранные протоколом пограничного шлюза, в конечном итоге к стабильному состоянию для заданного набора предпочтений пути. ^[46]
Детерминированная логика ограничений (неограниченная) ^[47]
Динамическая надежность графика. ^[22]
Игра-раскраска графов ^[48]
Узловая игра Кейлса и игра с формированием клик : ^[49] два игрока поочередно выбирают вершины, и индуцированный подграф должен быть независимым множеством (соответственно кликой). Побеждает тот, кто сыграет последним.
Недетерминированная логика ограничений (неограниченная) ^[11]

Другие

POMDP с конечным горизонтом (частично наблюдаемые марковские процессы принятия решений). ^[50]
Скрытые модели MDP (hmMDP). ^[51]
Динамический марковский процесс. ^[22]
Обнаружение зависимостей включения в реляционной базе данных ^[52]
Вычисление любого равновесия по Нэшу для двух игроков в игре нормальной формы , которое может быть получено с помощью алгоритма Лемке-Хаусона . ^[53]
Задача об облицовке коридора: дан набор плиток Ванга , выбранная плитка $T_{0}$ и ширина $n$ заданное в унарной записи, есть ли высота $m$ такой, что $n\times m$ прямоугольник можно разложить так, чтобы все границы плитки были $T_{0}$ ? ^[54]^[55]

См. также

Список NP-полных задач

Примечания

^ Р. А. Хирн (2 февраля 2005 г.). «Amazons полностью поддерживает PSPACE». arXiv : cs.CC/0502013 .
^ Маркус Хольцер и Стефан Швун (февраль 2004 г.). «Собирать молекулы в ATOMIX сложно» . Теоретическая информатика . 313 (3): 447–462. дои : 10.1016/j.tcs.2002.11.002 .
^ Авиезри С. Френкель (1978). «Сложность шашек на доске N x N – предварительный отчет». Материалы 19-го ежегодного симпозиума по информатике : 55–64.
^ Эрик Д. Демейн (2009). Сложность головоломки телескопа Дайсона . Том. Игры без шансов 3.
^ Перейти обратно: ^а ^б Роберт А. Хирн (2008). «Amazons, Konane и Cross Purposes являются PSPACE-полными». Игры без шансов 3 .
^ Лихтенштейн; Сипсер (1980). «Go — это полиномиальная сложность» . Журнал Ассоциации вычислительной техники . 27 (2): 393–401. дои : 10.1145/322186.322201 . S2CID 29498352 .
^ Лестницы Go полностью укомплектованы PSPACE. Архивировано 30 сентября 2007 г. на Wayback Machine.
^ Стефан Райш (1980). «Gobang ist PSPACE-vollstandig (Гомоку является PSPACE-полным)». Акта Информатика . 13 : 59–66. дои : 10.1007/bf00288536 . S2CID 21455572 .
^ Стефан Райш (1981). «Hex является PSPACE-полным». Acta Informatica (15): 167–191.
^ Вильетта, Джованни (2015). «Лемминги полны PSPACE» (PDF) . Теоретическая информатика . 586 : 120–134. arXiv : 1202.6581 . дои : 10.1016/j.tcs.2015.01.055 .
^ Перейти обратно: ^а ^б ^с ^д Эрик Д. Демейн; Роберт А. Хирн (2009). Игры с алгоритмами: алгоритмико-комбинаторная теория игр . Том. Игры без шансов 3.
^ Гриер, Дэниел (2013). «Определение победителя в произвольной игре с конечными множествами является PSPACE-завершенным». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 7965. стр. 497–503. arXiv : 1209.1750 . дои : 10.1007/978-3-642-39206-1_42 . ISBN 978-3-642-39205-4 . S2CID 13129445 .
^ Сигэки Ивата и Такуми Касаи (1994). «Игра «Отелло» на доске n*n является PSPACE-полной» . Теоретическая информатика . 123 (2): 329–340. дои : 10.1016/0304-3975(94)90131-7 .
^ Перейти обратно: ^а ^б ^с Хирн; Демейн (2002). «PSPACE-полнота головоломок со скользящими блоками и других проблем с помощью логической модели вычислений с недетерминированными ограничениями». arXiv : cs.CC/0205005 .
^ А. Кондон , Дж. Фейгенбаум, К. Лунд и П. Шор , Случайные участники дебатов и сложность аппроксимации стохастических функций, SIAM Journal on Computing 26:2 (1997) 369-400.
^ Лампис, Майкл; Мицу, Валя; Солтыс, Каролина (2015). «Scrabble является PSPACE-полным» . Журнал обработки информации .
^ Демейн, Эрик Д.; Вильетта, Джованни; Уильямс, Аарон (июнь 2016 г.). «Super Mario Bros. сложнее/проще, чем мы думали» (PDF) . 8-я Международная конференция «Развлечение с алгоритмами» .
Краткое содержание: Сабри, Нямат (28 апреля 2020 г.). «Super Mario Bros сложнее/проще, чем мы думали» . Середина .
^ Гилберт, Ленгауэр и Р.Э. Тарьян: Проблема камешек решена в полиномиальном пространстве. SIAM Journal on Computing, том 9, выпуск 3, 1980 г., страницы 513–524.
^ Филипп Хертель и Тонианн Питасси : Черно-белая галька завершена PSPACE. Архивировано 8 июня 2011 г. на Wayback Machine.
^ Перейти обратно: ^а ^б Такуми Касаи, Акео Адачи и Сигеки Ивата: Классы игр с камушками и полные задачи , SIAM Journal on Computing, том 8, 1979, страницы 574–586.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к К. Вагнер и Г. Вексунг. Вычислительная сложность . Д. Рейделя , 1986. Издательство ISBN 90-277-2146-7
^ Перейти обратно: ^а ^б ^с Христос Пападимитриу (1985). «Игры против природы» . Журнал компьютерных и системных наук . 31 (2): 288–301. дои : 10.1016/0022-0000(85)90045-5 .
^ А.П.Систла и Эдмунд М. Кларк (1985). «Сложность пропозициональной линейной темпоральной логики» . Журнал АКМ . 32 (3): 733–749. дои : 10.1145/3828.3837 . S2CID 47217193 .
^ Целочисленная оценка схемы
^ Гари и Джонсон (1979) , AL3.
^ Гари и Джонсон (1979) , AL4.
^ Гари и Джонсон (1979) , AL2.
^ Галил, З. Иерархии полных задач . В Acta Informatica 6 (1976), 77–88.
^ Гари и Джонсон (1979) , AL1.
^ Л. Дж. Стокмейер и А. Р. Мейер. Словесные задачи, требующие экспоненциального времени. В материалах 5-го симпозиума по теории вычислений, страницы 1–9, 1973 г.
^ Дж. Э. Хопкрофт и Дж. Д. Ульман. Введение в теорию автоматов, языки и вычисления , первое издание, 1979 г.
^ Перейти обратно: ^а ^б Д. Козен. Нижние оценки для систем естественных доказательств. В Proc. 18-й Симп. «Основы информатики», страницы 254–266, 1977 г.
↑ Проблема Лэнгтона с муравьями. Архивировано 27 сентября 2007 г. в Wayback Machine , «Обобщенная симметричная задача Лэнгтона с муравьями является PSPACE-полной» ЯМАГУЧИ ЭЙДЗИ и ЦУКИДЗИ ТАЦУИЭ в Техническом отчете IEIC ( Институт инженеров электроники, информации и связи ).
^ Т. Цзян и Б. Равикумар. Минимальные задачи NFA сложны. SIAM Journal on Computing, 22(6):1117–1141, декабрь 1993 г.
^ С.-Ю. Курода, «Классы языков и линейно ограниченные автоматы», Information and Control , 7 (2): 207–223, июнь 1964 г.
^ Бернацкий, Ласло. «Отсутствие звезд в регулярных выражениях является PSPACE-Complete» (PDF) . Проверено 13 января 2021 г.
^ Гари и Джонсон (1979) , AL12.
^ Гари и Джонсон (1979) , AL13.
^ Гари и Джонсон (1979) , AL14.
^ Гари и Джонсон (1979) , AL16.
^ Гари и Джонсон (1979) , AL19.
^ Гари и Джонсон (1979) , AL21.
^ Антонио Лозано и Хосе Л. Балькасар. Сложность графических задач для кратко представленных графов. В Манфреде Нагле, редакторе книги «Теоретико-графовые концепции в информатике», 15-й международный семинар, WG'89, номер 411 в «Конспектах лекций по информатике», страницы 277–286. Спрингер-Верлаг, 1990.
^ Дж. Фейгенбаум, С. Каннан, М. И. Варди и М. Вишванатан, Сложность проблем на графах, представленных в виде OBDD, Чикагский журнал теоретической информатики, том 5, № 5, 1999.
^ CH Пападимитриу; М. Яннакакис (1989). «Кратчайшие пути без карты». Конспекты лекций по информатике . Учеб. 16-й ИКАЛП. Том. 372. Шпрингер-Верлаг . стр. 610–620.
^ Алекс Фабрикант и Христос Пападимитриу . Сложность игровой динамики: колебания BGP, стоковые равновесия и многое другое. Архивировано 5 сентября 2008 г. в Wayback Machine . В СОДА 2008.
^ Эрик Д. Демейн и Роберт А. Хирн (23–26 июня 2008 г.). Логика ограничений: унифицированная основа для моделирования вычислений в виде игр . Том. Материалы 23-й ежегодной конференции IEEE по сложности вычислений (Complexity 2008). Колледж-Парк, Мэриленд. стр. 149–162. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Коста, Эуринардо; Пессоа, Виктор Лаге; Соарес, Ронан; Сампайо, Рудини (2020). «PSPACE-полнота двух игр-раскрасок графов». Теоретическая информатика . 824–825: 36–45. дои : 10.1016/j.tcs.2020.03.022 . S2CID 218777459 .
^ Шефер, Томас Дж. (1978). «О сложности некоторых игр двух лиц с совершенной информацией» . Журнал компьютерных и системных наук . 16 (2): 185–225. дои : 10.1016/0022-0000(78)90045-4 .
^ CH Пападимитриу; Ю. Н. Цициклис (1987). «Сложность марковских процессов принятия решений» (PDF) . Математика исследования операций . 12 (3): 441–450. дои : 10.1287/moor.12.3.441 . hdl : 1721.1/2893 .
^ И. Чадес; Дж. Карвардин; Т.Г. Мартин; С. Николь; Р. Саббадин; О. Баффе (2012). MOMDP: решение для моделирования проблем адаптивного управления . АААИ'12.
^ Казанова, Марко А.; и др. (1984). «Включительные зависимости и их взаимодействие с функциональными зависимостями» . Журнал компьютерных и системных наук . 28 : 29–59. дои : 10.1016/0022-0000(84)90075-8 .
^ П. В. Голдберг, К. Х. Пападимитриу и Р. Савани (2011). Сложность гомотопического метода, подбора равновесия и решений Лемке–Хаусона . Учеб. 52-й ФОКС. ИИЭЭ . стр. 67–76.
^ Мартен Маркс (2007). «Сложность модальной логики». В Патрике Блэкберне; Йохан ФАК ван Бентем; Фрэнк Уолтер (ред.). Справочник по модальной логике . Эльзевир. п. 170.
^ Льюис, Гарри Р. (1978). Сложность разрешимых случаев решения задачи исчисления предикатов . 19-й ежегодный симпозиум по основам информатики. IEEE. стр. 35–47.

Ссылки

[1] Р. А. Хирн (2 февраля 2005 г.). «Amazons полностью поддерживает PSPACE». arXiv : cs.CC/0502013 .

[2] Маркус Хольцер и Стефан Швун (февраль 2004 г.). «Собирать молекулы в ATOMIX сложно» . Теоретическая информатика . 313 (3): 447–462. дои : 10.1016/j.tcs.2002.11.002 .

[3] Авиезри С. Френкель (1978). «Сложность шашек на доске N x N – предварительный отчет». Материалы 19-го ежегодного симпозиума по информатике : 55–64.

[4] Эрик Д. Демейн (2009). Сложность головоломки телескопа Дайсона . Том. Игры без шансов 3.

[GONC3Hearn-5] Перейти обратно: ^а ^б Роберт А. Хирн (2008). «Amazons, Konane и Cross Purposes являются PSPACE-полными». Игры без шансов 3 .

[6] Лихтенштейн; Сипсер (1980). «Go — это полиномиальная сложность» . Журнал Ассоциации вычислительной техники . 27 (2): 393–401. дои : 10.1145/322186.322201 . S2CID 29498352 .

[goladder-7] Лестницы Go полностью укомплектованы PSPACE. Архивировано 30 сентября 2007 г. на Wayback Machine.

[Reisch1980-8] Стефан Райш (1980). «Gobang ist PSPACE-vollstandig (Гомоку является PSPACE-полным)». Акта Информатика . 13 : 59–66. дои : 10.1007/bf00288536 . S2CID 21455572 .

[9] Стефан Райш (1981). «Hex является PSPACE-полным». Acta Informatica (15): 167–191.

[10] Вильетта, Джованни (2015). «Лемминги полны PSPACE» (PDF) . Теоретическая информатика . 586 : 120–134. arXiv : 1202.6581 . дои : 10.1016/j.tcs.2015.01.055 .

[AlgorithmicGameTheory-11] Перейти обратно: ^а ^б ^с ^д Эрик Д. Демейн; Роберт А. Хирн (2009). Игры с алгоритмами: алгоритмико-комбинаторная теория игр . Том. Игры без шансов 3.

[Grier2012-12] Гриер, Дэниел (2013). «Определение победителя в произвольной игре с конечными множествами является PSPACE-завершенным». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 7965. стр. 497–503. arXiv : 1209.1750 . дои : 10.1007/978-3-642-39206-1_42 . ISBN 978-3-642-39205-4 . S2CID 13129445 .

[13] Сигэки Ивата и Такуми Касаи (1994). «Игра «Отелло» на доске n*n является PSPACE-полной» . Теоретическая информатика . 123 (2): 329–340. дои : 10.1016/0304-3975(94)90131-7 .

[ncl-14] Перейти обратно: ^а ^б ^с Хирн; Демейн (2002). «PSPACE-полнота головоломок со скользящими блоками и других проблем с помощью логической модели вычислений с недетерминированными ограничениями». arXiv : cs.CC/0205005 .

[randshang-15] А. Кондон , Дж. Фейгенбаум, К. Лунд и П. Шор , Случайные участники дебатов и сложность аппроксимации стохастических функций, SIAM Journal on Computing 26:2 (1997) 369-400.

[16] Лампис, Майкл; Мицу, Валя; Солтыс, Каролина (2015). «Scrabble является PSPACE-полным» . Журнал обработки информации .

[smb-17] Демейн, Эрик Д.; Вильетта, Джованни; Уильямс, Аарон (июнь 2016 г.). «Super Mario Bros. сложнее/проще, чем мы думали» (PDF) . 8-я Международная конференция «Развлечение с алгоритмами» .
Краткое содержание: Сабри, Нямат (28 апреля 2020 г.). «Super Mario Bros сложнее/проще, чем мы думали» . Середина .

[18] Гилберт, Ленгауэр и Р.Э. Тарьян: Проблема камешек решена в полиномиальном пространстве. SIAM Journal on Computing, том 9, выпуск 3, 1980 г., страницы 513–524.

[19] Филипп Хертель и Тонианн Питасси : Черно-белая галька завершена PSPACE. Архивировано 8 июня 2011 г. на Wayback Machine.

[pebble-20] Перейти обратно: ^а ^б Такуми Касаи, Акео Адачи и Сигеки Ивата: Классы игр с камушками и полные задачи , SIAM Journal on Computing, том 8, 1979, страницы 574–586.

[WagnerW-21] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к К. Вагнер и Г. Вексунг. Вычислительная сложность . Д. Рейделя , 1986. Издательство ISBN 90-277-2146-7

[papadimitriou85games-22] Перейти обратно: ^а ^б ^с Христос Пападимитриу (1985). «Игры против природы» . Журнал компьютерных и системных наук . 31 (2): 288–301. дои : 10.1016/0022-0000(85)90045-5 .

[SistlaAndClarke-23] А.П.Систла и Эдмунд М. Кларк (1985). «Сложность пропозициональной линейной темпоральной логики» . Журнал АКМ . 32 (3): 733–749. дои : 10.1145/3828.3837 . S2CID 47217193 .

[integercircuit-24] Целочисленная оценка схемы

[FOOTNOTEGareyJohnson1979AL3-25] Гари и Джонсон (1979) , AL3.

[FOOTNOTEGareyJohnson1979AL4-26] Гари и Джонсон (1979) , AL4.

[FOOTNOTEGareyJohnson1979AL2-27] Гари и Джонсон (1979) , AL2.

[GalilHierarch-28] Галил, З. Иерархии полных задач . В Acta Informatica 6 (1976), 77–88.

[FOOTNOTEGareyJohnson1979AL1-29] Гари и Джонсон (1979) , AL1.

[30] Л. Дж. Стокмейер и А. Р. Мейер. Словесные задачи, требующие экспоненциального времени. В материалах 5-го симпозиума по теории вычислений, страницы 1–9, 1973 г.

[31] Дж. Э. Хопкрофт и Дж. Д. Ульман. Введение в теорию автоматов, языки и вычисления , первое издание, 1979 г.

[D._Kozen_1977-32] Перейти обратно: ^а ^б Д. Козен. Нижние оценки для систем естественных доказательств. В Proc. 18-й Симп. «Основы информатики», страницы 254–266, 1977 г.

[33] Проблема Лэнгтона с муравьями. Архивировано 27 сентября 2007 г. в Wayback Machine , «Обобщенная симметричная задача Лэнгтона с муравьями является PSPACE-полной» ЯМАГУЧИ ЭЙДЗИ и ЦУКИДЗИ ТАЦУИЭ в Техническом отчете IEIC ( Институт инженеров электроники, информации и связи ).

[34] Т. Цзян и Б. Равикумар. Минимальные задачи NFA сложны. SIAM Journal on Computing, 22(6):1117–1141, декабрь 1993 г.

[35] С.-Ю. Курода, «Классы языков и линейно ограниченные автоматы», Information and Control , 7 (2): 207–223, июнь 1964 г.

[36] Бернацкий, Ласло. «Отсутствие звезд в регулярных выражениях является PSPACE-Complete» (PDF) . Проверено 13 января 2021 г.

[FOOTNOTEGareyJohnson1979AL12-37] Гари и Джонсон (1979) , AL12.

[FOOTNOTEGareyJohnson1979AL13-38] Гари и Джонсон (1979) , AL13.

[FOOTNOTEGareyJohnson1979AL14-39] Гари и Джонсон (1979) , AL14.

[FOOTNOTEGareyJohnson1979AL16-40] Гари и Джонсон (1979) , AL16.

[FOOTNOTEGareyJohnson1979AL19-41] Гари и Джонсон (1979) , AL19.

[FOOTNOTEGareyJohnson1979AL21-42] Гари и Джонсон (1979) , AL21.

[43] Антонио Лозано и Хосе Л. Балькасар. Сложность графических задач для кратко представленных графов. В Манфреде Нагле, редакторе книги «Теоретико-графовые концепции в информатике», 15-й международный семинар, WG'89, номер 411 в «Конспектах лекций по информатике», страницы 277–286. Спрингер-Верлаг, 1990.

[44] Дж. Фейгенбаум, С. Каннан, М. И. Варди и М. Вишванатан, Сложность проблем на графах, представленных в виде OBDD, Чикагский журнал теоретической информатики, том 5, № 5, 1999.

[45] CH Пападимитриу; М. Яннакакис (1989). «Кратчайшие пути без карты». Конспекты лекций по информатике . Учеб. 16-й ИКАЛП. Том. 372. Шпрингер-Верлаг . стр. 610–620.

[46] Алекс Фабрикант и Христос Пападимитриу . Сложность игровой динамики: колебания BGP, стоковые равновесия и многое другое. Архивировано 5 сентября 2008 г. в Wayback Machine . В СОДА 2008.

[47] Эрик Д. Демейн и Роберт А. Хирн (23–26 июня 2008 г.). Логика ограничений: унифицированная основа для моделирования вычислений в виде игр . Том. Материалы 23-й ежегодной конференции IEEE по сложности вычислений (Complexity 2008). Колледж-Парк, Мэриленд. стр. 149–162. {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[48] Коста, Эуринардо; Пессоа, Виктор Лаге; Соарес, Ронан; Сампайо, Рудини (2020). «PSPACE-полнота двух игр-раскрасок графов». Теоретическая информатика . 824–825: 36–45. дои : 10.1016/j.tcs.2020.03.022 . S2CID 218777459 .

[49] Шефер, Томас Дж. (1978). «О сложности некоторых игр двух лиц с совершенной информацией» . Журнал компьютерных и системных наук . 16 (2): 185–225. дои : 10.1016/0022-0000(78)90045-4 .

[50] CH Пападимитриу; Ю. Н. Цициклис (1987). «Сложность марковских процессов принятия решений» (PDF) . Математика исследования операций . 12 (3): 441–450. дои : 10.1287/moor.12.3.441 . hdl : 1721.1/2893 .

[51] И. Чадес; Дж. Карвардин; Т.Г. Мартин; С. Николь; Р. Саббадин; О. Баффе (2012). MOMDP: решение для моделирования проблем адаптивного управления . АААИ'12.

[52] Казанова, Марко А.; и др. (1984). «Включительные зависимости и их взаимодействие с функциональными зависимостями» . Журнал компьютерных и системных наук . 28 : 29–59. дои : 10.1016/0022-0000(84)90075-8 .

[53] П. В. Голдберг, К. Х. Пападимитриу и Р. Савани (2011). Сложность гомотопического метода, подбора равновесия и решений Лемке–Хаусона . Учеб. 52-й ФОКС. ИИЭЭ . стр. 67–76.

[54] Мартен Маркс (2007). «Сложность модальной логики». В Патрике Блэкберне; Йохан ФАК ван Бентем; Фрэнк Уолтер (ред.). Справочник по модальной логике . Эльзевир. п. 170.

[55] Льюис, Гарри Р. (1978). Сложность разрешимых случаев решения задачи исчисления предикатов . 19-й ежегодный симпозиум по основам информатики. IEEE. стр. 35–47.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]