Список задач PSPACE-complete

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

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

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

Амазонки ^[1]
Атомикс ^[2]
Шашки , если ничья вынуждена после полиномиального числа ходов без прыжка ^[3]
Игра «Телескоп Дайсона» ^[4]
Перекрестные цели ^[5]
География
Версия Instant Insanity для двух игроков
Ко -фри Го ^[6]
Захват лестницы в Го ^[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]
Регулярное выражение Star-Freeness ^[36]
Проблема эквивалентности регулярных выражений ^[21]
Проблема пустоты для регулярных выражений с пересечением. ^[21]
Проблема эквивалентности для регулярных выражений без звезд с возведением в квадрат. ^[21]
Покрытие для линейных грамматик ^[37]
Структурная эквивалентность для линейных грамматик ^[38]
Проблема эквивалентности для регулярных грамматик ^[39]
Проблема пустоты для грамматик ET0L ^[40]
Текстовая задача для грамматик ET0L ^[41]
Проблема принадлежности языка древовидного преобразователя для нисходящих конечно-уровневых древовидных преобразователей ^[42]

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

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

Другие

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

Смотрите также

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

Примечания

^ RA Hearn (2 февраля 2005 г.). «Amazons — это PSPACE-complete». arXiv : cs.CC/0502013 .
^ Маркус Хольцер и Стефан Швун (февраль 2004 г.). «Сборка молекул в ATOMIX — это сложно». Теоретическая информатика . 313 (3): 447–462. doi : 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 is polynomial-space hard». Журнал Ассоциации вычислительной техники . 27 (2): 393–401. doi : 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 ist PSPACE-vollständig (Hex является PSPACE-полным)». Акта Информатика (15): 167–191.
^ Виглиетта, Джованни (2015). «Lemmings Is PSPACE-Complete» (PDF) . Теоретическая информатика . 586 : 120–134. arXiv : 1202.6581 . doi : 10.1016/j.tcs.2015.01.055 .
^ abcd Эрик Д. Демейн; Роберт А. Хирн (2009). Игры с алгоритмами: алгоритмическая комбинаторная теория игр. Том. Игры без шансов 3.
^ Грир, Дэниел (2013). «Определение победителя произвольной конечной игры с частично упорядоченными множествами является PSPACE-полным». Автоматы, языки и программирование . Конспект лекций по информатике. Том 7965. С. 497–503. arXiv : 1209.1750 . doi :10.1007/978-3-642-39206-1_42. ISBN 978-3-642-39205-4. S2CID 13129445.
^ Шигеки Ивата и Такуми Касаи (1994). «Игра «Отелло» на доске n*n является PSPACE-полной». Теоретическая информатика . 123 (2): 329–340. doi : 10.1016/0304-3975(94)90131-7 .
^ abc Hearn ; Demaine (2002). "PSPACE-полнота головоломок со скользящими блоками и других задач с помощью недетерминированной модели логики ограничений вычислений". arXiv : cs.CC/0205005 .
^ А. Кондон , Дж. Фейгенбаум, К. Лунд и П. Шор , Случайные спорщики и сложность аппроксимации стохастических функций, SIAM Journal on Computing 26:2 (1997) 369-400.
^ Лампис, Майкл; Мицу, Валя; Солтыс, Каролина (2015). «Scrabble is PSPACE-complete». Журнал обработки информации .
^ Демейн, Эрик Д.; Виглиетта, Джованни; Уильямс, Аарон (июнь 2016 г.). «Super Mario Bros. сложнее/проще, чем мы думали» (PDF) . 8-я международная конференция по развлечениям с алгоритмами .
Краткое содержание: Сабри, Нимат (28 апреля 2020 г.). «Super Mario Bros сложнее/легче, чем мы думали». Medium .
^ Гилберт, Ленгауэр и Р. Э. Тарьян: Задача о булыжниках полна в полиномиальном пространстве. Журнал SIAM по вычислениям, том 9, выпуск 3, 1980, страницы 513-524.
^ Филипп Хертель и Тонианн Питасси : Черно-белая галька — это PSPACE-Complete Архивировано 08.06.2011 на Wayback Machine
^ ab Такуми Касаи, Акео Адачи и Шигеки Ивата: Классы игр с камешками и полные задачи , Журнал SIAM по вычислениям, том 8, 1979, страницы 574-586.
^ abcdefghijk К. Вагнер и Г. Вексунг. Вычислительная сложность . D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7
^ abc Христос Пападимитриу (1985). «Игры против природы». Журнал компьютерных и системных наук . 31 (2): 288–301. doi : 10.1016/0022-0000(85)90045-5 .
^ APSistla и Эдмунд М. Кларк (1985). «Сложность пропозициональных линейных временных логик». Журнал ACM . 32 (3): 733–749. doi : 10.1145/3828.3837 . S2CID 47217193.
^ Оценка целочисленной схемы
^ Гари и Джонсон (1979), AL3.
^ Гари и Джонсон (1979), AL4.
^ Гари и Джонсон (1979), AL2.
^ Галил, З. Иерархии полных проблем . В Acta Informatica 6 (1976), 77-88.
^ Гари и Джонсон (1979), AL1.
^ LJ Stockmeyer и AR Meyer. Текстовые задачи, требующие экспоненциального времени. В трудах 5-го симпозиума по теории вычислений, страницы 1–9, 1973.
^ Дж. Э. Хопкрофт и Дж. Д. Ульман. Введение в теорию автоматов, языки и вычисления , первое издание, 1979.
^ ab D. Kozen. Нижние оценки для систем естественных доказательств. В Proc. 18th Symp. on the Foundations of Computer Science, страницы 254–266, 1977.
^ Задача о муравье Лэнгтона Архивировано 27 сентября 2007 г. на Wayback Machine , «Обобщенная симметричная задача о муравье Лэнгтона является PSPACE-полной» ЯМАГУТИ ЭЙДЖИ и ЦУКИДЖИ ТАЦУИЭ в Техническом отчете IEIC ( Институт инженеров электроники, информации и связи )
^ T. Jiang и B. Ravikumar. Минимальные проблемы NFA сложны. SIAM Journal on Computing, 22(6):1117–1141, декабрь 1993 г.
^ С.-Я. Курода, «Классы языков и линейно-ограниченные автоматы», Информация и управление , 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 в Lecture Notes in Computer Science, страницы 277–286. Springer-Verlag, 1990.
^ Дж. Фейгенбаум, С. Каннан, М.Ю. Варди и М. Вишванатан, Сложность задач на графах, представленных в виде OBDD, Чикагский журнал теоретической информатики, т. 5, № 5, 1999.
^ CH Papadimitriou; M. Yannakakis (1989). «Кратчайшие пути без карты». Lecture Notes in Computer Science . Proc. 16th ICALP. Vol. 372. Springer-Verlag . pp. 610–620.
^ Алекс Фабрикант и Христос Пападимитриу . Сложность динамики игры: колебания BGP, равновесие стока и не только. Архивировано 05.09.2008 на Wayback Machine . В SODA 2008.
^ Эрик Д. Демейн; Роберт А. Хирн (23–26 июня 2008 г.). Constraint Logic: A Uniform Framework for Modeling Computation as Games. Том. Труды 23-й ежегодной конференции IEEE по вычислительной сложности (Complexity 2008). Колледж-Парк, Мэриленд. С. 149–162.{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )
^ Коста, Эуринардо; Пессоа, Виктор Лаге; Соарес, Ронан; Сампайо, Рудини (2020). «PSPACE-полнота двух игр по раскраске графов». Теоретическая информатика . 824–825: 36–45. doi :10.1016/j.tcs.2020.03.022. S2CID 218777459.
^ Шефер, Томас Дж. (1978). «О сложности некоторых игр двух лиц с полной информацией». Журнал компьютерных и системных наук . 16 (2): 185–225. doi : 10.1016/0022-0000(78)90045-4 .
^ CH Papadimitriou; JN Tsitsiklis (1987). "Сложность марковских процессов принятия решений" (PDF) . Математика исследования операций . 12 (3): 441–450. doi :10.1287/moor.12.3.441. hdl : 1721.1/2893 .
^ I. Chades; J. Carwardine; TG Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDP: решение для моделирования проблем адаптивного управления . AAAI'12.
^ Casanova, Marco A.; et al. (1984). «Зависимости включения и их взаимодействие с функциональными зависимостями». Журнал компьютерных и системных наук . 28 : 29–59. doi : 10.1016/0022-0000(84)90075-8 .
^ PW Goldberg и CH Papadimitriou и R. Savani (2011). Сложность метода гомотопии, выбор равновесия и решения Лемке–Хаусона . Труды 52-й конференции FOCS. IEEE . стр. 67–76.
^ Maarten Marx (2007). «Сложность модальной логики». В Patrick Blackburn; Johan FAK van Benthem; Frank Wolter (ред.). Handbook of Modal Logic . Elsevier. стр. 170.
^ Льюис, Гарри Р. (1978). Сложность разрешимых случаев проблемы принятия решений для исчисления предикатов . 19-й ежегодный симпозиум по основам компьютерной науки. IEEE. С. 35–47.

Ссылки

Garey, MR ; Johnson, DS (1979). Компьютеры и неразрешимость: Руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 978-0-7167-1045-5.
Страница Эппштейна о вычислительной сложности игр
Сложность аппроксимации PSPACE-полных задач для иерархических спецификаций

[1] RA Hearn (2 февраля 2005 г.). «Amazons — это PSPACE-complete». arXiv : cs.CC/0502013 .

[2] Маркус Хольцер и Стефан Швун (февраль 2004 г.). «Сборка молекул в ATOMIX — это сложно». Теоретическая информатика . 313 (3): 447–462. doi : 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 is polynomial-space hard». Журнал Ассоциации вычислительной техники . 27 (2): 393–401. doi : 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 ist PSPACE-vollständig (Hex является PSPACE-полным)». Акта Информатика (15): 167–191.

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

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

[Grier2012-12] Грир, Дэниел (2013). «Определение победителя произвольной конечной игры с частично упорядоченными множествами является PSPACE-полным». Автоматы, языки и программирование . Конспект лекций по информатике. Том 7965. С. 497–503. arXiv : 1209.1750 . doi :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. doi : 10.1016/0304-3975(94)90131-7 .

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

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

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

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

[18] Гилберт, Ленгауэр и Р. Э. Тарьян: Задача о булыжниках полна в полиномиальном пространстве. Журнал SIAM по вычислениям, том 9, выпуск 3, 1980, страницы 513-524.

[19] Филипп Хертель и Тонианн Питасси : Черно-белая галька — это PSPACE-Complete Архивировано 08.06.2011 на Wayback Machine

[pebble-20] Такуми Касаи, Акео Адачи и Шигеки Ивата: Классы игр с камешками и полные задачи , Журнал SIAM по вычислениям, том 8, 1979, страницы 574-586.

[WagnerW-21] К. Вагнер и Г. Вексунг. Вычислительная сложность . D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7

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

[SistlaAndClarke-23] APSistla и Эдмунд М. Кларк (1985). «Сложность пропозициональных линейных временных логик». Журнал ACM . 32 (3): 733–749. doi : 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] LJ Stockmeyer и AR Meyer. Текстовые задачи, требующие экспоненциального времени. В трудах 5-го симпозиума по теории вычислений, страницы 1–9, 1973.

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

[D._Kozen_1977-32] D. Kozen. Нижние оценки для систем естественных доказательств. В Proc. 18th Symp. on the Foundations of Computer Science, страницы 254–266, 1977.

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

[34] T. Jiang и B. Ravikumar. Минимальные проблемы NFA сложны. SIAM Journal on Computing, 22(6):1117–1141, декабрь 1993 г.

[35] С.-Я. Курода, «Классы языков и линейно-ограниченные автоматы», Информация и управление , 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 в Lecture Notes in Computer Science, страницы 277–286. Springer-Verlag, 1990.

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

[45] CH Papadimitriou; M. Yannakakis (1989). «Кратчайшие пути без карты». Lecture Notes in Computer Science . Proc. 16th ICALP. Vol. 372. Springer-Verlag . pp. 610–620.

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

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

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

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

[50] CH Papadimitriou; JN Tsitsiklis (1987). "Сложность марковских процессов принятия решений" (PDF) . Математика исследования операций . 12 (3): 441–450. doi :10.1287/moor.12.3.441. hdl : 1721.1/2893 .

[51] I. Chades; J. Carwardine; TG Martin; S. Nicol; R. Sabbadin; O. Buffet (2012). MOMDP: решение для моделирования проблем адаптивного управления . AAAI'12.

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

[53] PW Goldberg и CH Papadimitriou и R. Savani (2011). Сложность метода гомотопии, выбор равновесия и решения Лемке–Хаусона . Труды 52-й конференции FOCS. IEEE . стр. 67–76.

[54] Maarten Marx (2007). «Сложность модальной логики». В Patrick Blackburn; Johan FAK van Benthem; Frank Wolter (ред.). Handbook of Modal Logic . Elsevier. стр. 170.

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