Список неполадок, связанных с PSPACE

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

• 1 Игры и головоломки
• 2 Логика
• 3 Лямбда-исчисление
• 4 Автоматы и теория языков
  • 4.1 Теория схем
  • 4.2 Теория автоматов
  • 4.3 Формальные языки
• 5 Теория графов
• 6 Другое
• 7 См. Также
• 8 Примечания
• 9 Ссылки

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

• Амазонки
• Atomix
• Шашки
• География
• Ko - бесплатно Go
• Лестничный захват в Го
• Гомоку
• Hex
• Конане
• Лемминги
• Poset Game
• Реверси
• Час пик
• Поиск оптимальной игры в пасьянсе Маджонг
• Сокобан
• Super Mario Bros.
• Черный Игра Галька
• Черно-белый Игра Галька
• Ациклический игра в гальку
• для одного игрока игра в гальку
• Жетон на ациклическом ориентированном графе игры:
• Уничтожение
• Удар
• Захват
• Блокировка края
• Цель
• Преследование

• Количественные логические формулы
• Логика первого порядка из равенства
• Доказуемость в интуиционистской логике высказываний
• Сати Действие в модальной логике S4
• Теория первого порядка натуральных чисел при последующей операции
• Теория первого порядка натуральных чисел в стандартном порядке
• Теория первого порядка из целых чисел в стандартном порядке
• Теория первого порядка из хорошо упорядоченных множеств
• Теория первого порядка двоичных строк при лексикографическом порядке
• Теория первого порядка конечной булевой алгебры
• Стохастическая выполнимость
• Линейная временная логика выполнимость и проверка модели

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

Теория схем

Целочисленная схема оценка

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

• Word проблема для линейных ограниченных автоматов
• Word проблема для
• проблема пустоты для недетерминированной
• проблема эквивалентности для недетерминированные конечные автоматы
• Задача со словом и пустое слово проблема отсутствия стирания стековых автоматов
• Пустота пересечения неограниченного числа детерминированных конечных автоматов
• Обобщенная версия муравья Лэнгтона
• Минимизация недетерминированных конечных автоматов

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

• Проблема со словами для контекстно-зависимого языка
• Пустота пересечения для неограниченного количества регулярных языков
• Регулярное выражение звездная свобода
• Эквивалентность проблема для регулярных выражений
• проблема пустоты для регулярных выражений с пересечением.
• проблема эквивалентности для регулярных выражений без звезд с возведением в квадрат.
• Покрытие для линейных грамматик
• Структурная эквивалентность для линейных грамматик
• Проблема эквивалентности для Обычных грамматик
• Проблема пустоты для грамматики
• Word проблема для грамматик
• проблема принадлежности для преобразователей дерева с конечным числом состояний сверху вниз

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

• Конечная горизонт POMDP (частично наблюдаемые марковские процессы принятия решений).
• MDP со скрытой моделью (hmMDP).
• Динамический марковский процесс.
• Обнаружение зависимостей включения в реляционной базе данных
• Вычисление любого равновесия по Нэшу для 2-х игроков нормальной игры, которое может быть получено с помощью Лемке – Хаусона алгоритм.
• Проблема мозаики коридора: задан набор плиток Ванга, выбранная плитка $T\; 0\; \{\backslash \; displaystyle\; T\_\; \{0\}\}$и ширина $n\; \{\backslash \; displaystyle\; n\}$в унарном формате, существует ли высота $m\; \{\backslash \; displaystyle\; m\}$такая, что $n\; \times \; m\; \{\backslash \; displaystyle\; n\; \backslash \; times\; m\}$прямоугольник можно разбить на плитки так, чтобы все граничные плитки были $T\; 0\; \{\backslash \; displaystyle\; T\_\; \{0\}\}$?

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

1. ^Р. А. Хирн (02.02.2005). «Амазонки - это PSPACE-полная». 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. Для цитирования журнала требуется | journal =()
4. ^Эрик Д. Демейн (2009). Сложность системы Дайсона Головоломка с телескопом. Игры без шанса 3.
5. ^ Роберт А. Хирн (2008). «Амазонки, Конане и Cross Purposes полностью соответствуют PSPACE». Игры без шанса 3. Для цитирования требуется | journal =()
6. ^Lichtenstein; Sipser (1980). «Go - это сложная система в полиномиальном пространстве». Journal of the Association for Computing Machinery. 27 (2): 393– 401. doi : 10.1145 / 322186.322201.
7. ^Лестницы Go являются PSPACE-complete Архивировано 2007-09-30 на Wayback Machine
8. ^Стефан Райш (1980). «Gobang ist PSPACE-vollstandig (Gomoku - PSPACE-complete)». Acta Informatica. 13 : 59–66. doi : 10.1007 / bf00288536.
9. ^Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex is PSPACE-complete)». Acta Inform. (15): 167–191.
10. ^Viglietta, Giovanni (2015). «Лемминги» Завершено ли PSPACE " (PDF). Теоретическая информатика. 586 : 120–134. doi : 10.1016 / j.tcs.2015.01.055.
11. ^ Эрик Д. Демейн; Роберт А. Хирн (2009). Игры с алгоритмами: алгоритмическая комбинаторная теория игр. Игры без шанса 3.
12. ^Гриер, Дэниел (2012). «Определение победителя в произвольной игре с конечными точками - завершено для PSPACE». Автоматы, языки и программирование. Конспект лекций по информатике. 7965 . С. 497–503. arXiv : 1209.1750. DOI : 10.1007 / 978-3-642-39206-1_42. ISBN 978-3-642-39205-4.
13. ^Сигеки Ивата и Такуми Касаи (1994). «Игра« Отелло на н * пной доске »полностью завершена для PSPACE». Теоретическая информатика. 123 (2): 329–340. doi : 10.1016 / 0304-3975 (94) 90131-7.
14. ^ Хирн; Демейн (2002). «PSPACE-Полнота головоломок со скользящими блоками и другие проблемы посредством недетерминированной логической модели вычислений с ограничениями». arXiv : cs.CC/0205005.
15. ^A. Кондон, Дж. Фейгенбаум, К. Лунд и П. Шор, Случайные спорщики и трудность аппроксимации стохастических функций, SIAM Journal on Computing 26: 2 (1997) 369-400.
16. ^Демейн; Вильетта; Уильямс (2016). «Super Mario Bros. сложнее / проще, чем мы думали». Для цитирования журнала требуется | journal =()
17. ^Гилберт, Ленгауэр и Р. Э. Тарджан: проблема гальки решена in Polynomial Space. SIAM Journal on Computing, Volume 9, Issue 3, 1980, pages 513-524.
18. ^Филипп Хертель и Тониан Питасси : Черно-белая галька - это PSPACE-Complete Архивировано 08.06.2011 в Wayback Machine
19. ^ Такуми Касаи, Акео Адачи и Сигеки Ивата: классы Pebble Games и полные проблемы, SIAM Journal on Computing, Volume 8, 1979, страницы 574-586.
20. ^ К. Вагнер и Г. Вексунг. Вычислительная сложность. Д. Рейдел Publishing Company, 1986. ISBN 90-277 -2146-7
21. ^ Христос Пападимитриу (1985). «Игры против природы». Журнал компьютерных и системных наук. 31 (2): 288–301. doi : 10.1016 / 0022-0000 (85) 90045-5.
22. ^А.П.Систла и Эдмунд М. Кларк (1985). «Сложность пропозициональной линейной временной ло gics ". Журнал ACM. 32 (3): 733–749. doi : 10.1145 / 3828.3837.
23. ^Вычисление целочисленной схемы
24. ^Гэри-Джонсон: AL3
25. ^Гарей-Джонсон: AL4
26. ^Галил, З. Иерархии полных проблем. В Acta Informatica 6 (1976), 77-88.
27. ^Гэри-Джонсон: AL2
28. ^Л. Дж. Штокмейер и А. Р. Мейер. Проблемы со словами, требующие экспоненциального времени. В Трудах 5-го симпозиума по теории вычислений, страницы 1–9, 1973 г.
29. ^Гэри-Джонсон: AL1
30. ^J. Э. Хопкрофт и Дж. Д. Ульман. Введение в теорию автоматов, языки и вычисления, первое издание, 1979 г.
31. ^ D. Козен. Нижние оценки естественных систем доказательства. В Proc. 18-й симпозиум on the Foundations of Computer Science, pages 254–266, 1977.
32. ^Проблема Муравья Лэнгтона Архивировано 2007-09-27 в Wayback Machine, «Обобщенный симметричный алгоритм Лэнгтона. Проблема муравья завершена PSPACE "Ямагути Эидзи и Цукиджи Татсуи в (Институт инженеров электроники, информации и коммуникаций )
33. ^Т. Цзян и Б. Равикумар. Минимальные проблемы NFA сложны. SIAM Journal on Computing, 22 ( 6): 1117–1141, декабрь 1993 г.
34. ^С.-Й. Курода, «Классы языков и линейно-ограниченные автоматы», Информация и управление, 7 (2): 207–223, Июнь 1964 года.
35. ^Свобода регулярных выражений - полная PSPACE.
36. ^Гэри-Джонсон: AL12
37. ^Гэри-Джонсон: AL13
38. ^Гэри-Джонсон: AL14
39. ^Гэри-Джонсон: AL16
40. ^Garey – Johnson: AL19
41. ^Garey – Johnson: AL21
42. ^Антонио Лозано и Хосе Л. Бальказар. Сложность задач графа для лаконично представленных графов. In Manfred Nagl, редактор, Graph-Theoretic Concepts in Computer Science, 15th International Worksh op, WG’89, номер 411 в Lecture Notes in Computer Science, стр. 277–286. Springer-Verlag, 1990.
43. ^Дж. Файгенбаум, С. Каннан, М. Ю. Варди и М. Вишванатан, Сложность задач на графах, представленных в виде OBDD, Чикагский журнал теоретической информатики, том 5, № 5, 1999.
44. ^C.H. Пападимитриу; М. Яннакакис (1989). «Кратчайшие пути без карты». Конспект лекций по информатике. Proc. 16-й ИКАЛП. 372 . Спрингер-Верлаг. С. 610–620.
45. ^Алекс Фабрикант и Христос Пападимитриу. Сложность игровой динамики: колебания BGP, поглощение equlibria и т.д. Архивировано 5 сентября 2008 г. на Wayback Machine. В SODA 2008.
46. ^Эрик Д. Демейн и Роберт А. Хирн (23–26 июня 2008 г.). Логика ограничений: унифицированная структура для моделирования вычислений как игр. Материалы 23-й ежегодной конференции IEEE по вычислительной сложности (Complexity 2008). Колледж-Парк, Мэриленд. pp. 149–162.
47. ^C.H. Пападимитриу; J.N. Цициклис (1987). «Сложность марковских процессов принятия решений» (PDF). Математика исследования операций. 12 (3): 441–450. doi : 10.1287 / moor.12.3.441. hdl : 1721,1 / 2893.
48. ^I. Чейдс; Дж. Карвардин; T.G. Мартин; С. Николь; Р. Саббадин; О. Баффет (2012). MOMDPs: решение для моделирования проблем адаптивного управления. AAAI'12.
49. ^Casanova Marco A.; и другие. (1984). «Зависимости включения и их взаимодействие с функциональными зависимостями». Журнал компьютерных и системных наук. 28 : 29–59. doi : 10.1016 / 0022-0000 (84) 90075-8.
50. ^P.W. Голдберг и Ч. Пападимитриу и Р. Савани (2011). Сложность метода гомотопии, равновесного отбора и решений Лемке – Хаусона. Proc. 52-й FOCS. IEEE. С. 67–76.
51. ^Маартен Маркс (2007). «Сложность модальной логики». В Патрике Блэкберне; Йохан F.A.K. ван Бентем; Фрэнк Уолтер (ред.). Справочник по модальной логике. Эльзевир. п. 170.
52. ^Льюис, Гарри Р. (1978). Сложность разрешимых случаев задачи решения для исчисления предикатов. 19-й ежегодный симпозиум по основам информатики. IEEE. стр. 35–47.

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