Список задач 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]} ${\displaystyle T_{0}}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle n\times m}$ ${\displaystyle T_{0}}$

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

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

Примечания

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.
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.
7. Лестницы Go полностью соответствуют PSPACE. Архивировано 30 сентября 2007 г. на Wayback Machine.
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 .
11. Эрик Д. Демейн; Роберт А. Хирн (2009). Игры с алгоритмами: алгоритмическая комбинаторная теория игр. Том. Игры без шансов 3.
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 .
14. Hearn ; Demaine (2002). "PSPACE-полнота головоломок со скользящими блоками и других задач с помощью недетерминированной модели логики ограничений вычислений". arXiv : cs.CC/0205005 .
15. А. Кондон , Дж. Фейгенбаум, К. Лунд и П. Шор , Случайные спорщики и сложность аппроксимации стохастических функций, SIAM Journal on Computing 26:2 (1997) 369-400.
16. Лампис, Майкл; Мицу, Валя; Солтыс, Каролина (2015). «Scrabble is PSPACE-complete». Журнал обработки информации .
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
20. Такуми Касаи, Акео Адачи и Шигеки Ивата: Классы игр с камешками и полные задачи , Журнал SIAM по вычислениям, том 8, 1979, страницы 574-586.
21. К. Вагнер и Г. Вексунг. Вычислительная сложность . D. Reidel Publishing Company, 1986. ISBN 90-277-2146-7 
22. Христос Пападимитриу (1985). «Игры против природы». Журнал компьютерных и системных наук . 31 (2): 288–301. doi : 10.1016/0022-0000(85)90045-5 .
23. APSistla и Эдмунд М. Кларк (1985). «Сложность пропозициональных линейных временных логик». Журнал ACM . 32 (3): 733–749. doi : 10.1145/3828.3837 . S2CID  47217193.
24. Оценка целочисленной схемы
25. Гари и Джонсон (1979), AL3.
26. Гари и Джонсон (1979), AL4.
27. Гари и Джонсон (1979), AL2.
28. Галил, З. Иерархии полных проблем . В Acta Informatica 6 (1976), 77-88.
29. Гари и Джонсон (1979), AL1.
30. LJ Stockmeyer и AR Meyer. Текстовые задачи, требующие экспоненциального времени. В трудах 5-го симпозиума по теории вычислений, страницы 1–9, 1973.
31. Дж. Э. Хопкрофт и Дж. Д. Ульман. Введение в теорию автоматов, языки и вычисления , первое издание, 1979.
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 г.
37. Гари и Джонсон (1979), AL12.
38. Гари и Джонсон (1979), AL13.
39. Гари и Джонсон (1979), AL14.
40. Гари и Джонсон (1979), AL16.
41. Гари и Джонсон (1979), AL19.
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.

Ссылки

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