Список проблем PSPACE-complete - List of PSPACE-complete problems
Вот некоторые из наиболее распространенных проблем, которые PSPACE-полный когда выражается как проблемы решения. Этот список никоим образом не является исчерпывающим.
Игры и головоломки
Обобщенный версии:
- Амазонки[1]
- Атомикс[2]
- Шашки[3]
- Игра телескопа Дайсона[4]
- Перекрестные цели[5]
- География
- Ко -свободный Идти[6]
- Захват лестницы в Go[7]
- Гомоку[8]
- Hex[9]
- Конане[5]
- Лемминги[10]
- Узел Кейлс[11]
- Poset Game[12]
- Реверси[13]
- Переход через реку[14]
- Час пик[14]
- Поиск оптимальной игры в Пасьянс маджонг[15]
- Сокобан[14]
- Super Mario Bros.[16]
- Чернить Галька игра[17]
- Черно-белый Галька игра[18]
- Ациклический камешковая игра[19]
- Один игрок камешковая игра[19]
- Токен на ациклический ориентированный граф игры:[11]
- Аннигиляция
- Ударить
- Захватывать
- Блокировка края
- Цель
- Преследование
Логика
- Количественные булевы формулы
- Логика первого порядка из равенство[20]
- Доказуемость в интуиционистская логика высказываний
- Удовлетворение модальная логика S4[20]
- Теория первого порядка из натуральные числа при операции преемника[20]
- Теория первого порядка из натуральные числа под стандартный заказ[20]
- Теория первого порядка из целые числа под стандартный заказ[20]
- Теория первого порядка из упорядоченные наборы[20]
- Теория первого порядка из двоичные строки под лексикографический порядок[20]
- Теория первого порядка конечного Булева алгебра[20]
- Стохастическая выполнимость[21]
- Линейная временная логика выполнимость и проверка модели[22]
Лямбда-исчисление
Тип заселения проблема для просто типизированного лямбда-исчисления
Автоматы и теория языка
Теория схем
Целочисленная схема оценка[23]
Теория автоматов
- Проблема со словом для линейно ограниченные автоматы[24]
- Проблема со словом для квазиреальные автоматы[25]
- Проблема пустоты для недетерминированного двусторонний конечный автомат[26][27]
- Проблема эквивалентности для недетерминированные конечные автоматы[28][29]
- Проблема со словом и проблема с пустотой для не-стирания стековые автоматы[30]
- Пустота пересечения неограниченного числа детерминированные конечные автоматы[31]
- Обобщенная версия Муравей Лэнгтона[32]
- Сведение к минимуму недетерминированные конечные автоматы[33]
Формальные языки
- Проблема со словом для контекстно-зависимый язык[34]
- Пустота пересечения для неограниченного количества обычные языки [31]
- Регулярное выражение звездная свобода[35]
- Проблема эквивалентности за обычные выражения[20]
- Проблема пустоты за обычные выражения с пересечением.[20]
- Проблема эквивалентности без звезд обычные выражения с квадратом.[20]
- Покрытие для линейные грамматики[36]
- Структурная эквивалентность для линейные грамматики[37]
- Проблема эквивалентности за Обычные грамматики[38]
- Проблема пустоты за ET0L грамматики[39]
- Проблема со словом для ET0L грамматики[40]
- Язык преобразователя дерева проблема принадлежности для преобразователей дерева с конечным числом состояний сверху вниз[41]
Теория графов
- сжатые версии многих задач с графами, с графами, представленными в виде булевых схем,[42] упорядоченный диаграммы бинарных решений[43] или другие связанные заявления:
- проблема s-t достижимости для сжатых графов. По сути, это то же самое, что и простейшая проблема существования плана в автоматизированное планирование и составление графиков.
- планарность сжатых графов
- ацикличность сжатых графиков
- связность сжатых графов
- существование эйлеровых путей в кратком графе
- Проблема канадского путешественника.[44]
- Определение того, выбраны ли маршруты Протокол пограничного шлюза в конечном итоге придет к стабильному состоянию для данного набора предпочтений пути[45]
- Надежность динамического графа.[21]
- Детерминированный логика ограничений (неограниченный)[46]
- Недетерминированная логика ограничений (неограниченная)[11]
- Ограниченная логика ограничений для двух игроков[11]
Другие
- Конечные горизонтальные POMDP (частично наблюдаемые марковские процессы принятия решений).[47]
- Скрытые модели MDP (hmMDP).[48]
- Динамический марковский процесс.[21]
- Обнаружение зависимостей включения в реляционной базе данных[49]
- Расчет любых равновесие по Нэшу 2-х игроков игра в нормальной форме, который можно получить через Алгоритм Лемке – Хаусона.[50]
- Проблема плитки коридора: с учетом набора Ванская плитка, выбранная плитка и ширина даны в унарных обозначениях, есть ли высота так что прямоугольник можно выложить плиткой так, чтобы все граничные плитки были ?[51][52]
Смотрите также
Примечания
- ^ Р. А. Хирн (2 февраля 2005 г.). «Амазонки - это 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.
- ^ Лестницы Go являются PSPACE-complete В архиве 2007-09-30 на Wayback Machine
- ^ Стефан Райш (1980). «Gobang ist PSPACE-vollstandig (Gomoku - PSPACE-complete)». Acta Informatica. 13: 59–66. Дои:10.1007 / bf00288536.
- ^ Стефан Райш (1981). «Hex ist PSPACE-vollständig (Hex ist PSPACE-complete)». Акта Информ. (15): 167–191.
- ^ Вильетта, Джованни (2015). «Лемминги - это PSPACE-Complete» (PDF). Теоретическая информатика. 586: 120–134. Дои:10.1016 / j.tcs.2015.01.055.
- ^ а б c d Эрик Д. Демейн; Роберт А. Хирн (2009). Игры с алгоритмами: алгоритмическая комбинаторная теория игр. Игры без шанса 3.
- ^ Гриер, Дэниел (2012). «Определение победителя в произвольной игре с конечными точками - завершено для PSPACE». Автоматы, языки и программирование. Конспект лекций по информатике. 7965. С. 497–503. arXiv:1209.1750. Дои:10.1007/978-3-642-39206-1_42. ISBN 978-3-642-39205-4.
- ^ Сигеки Ивата и Такуми Касаи (1994). «Игра« Отелло на н * пной доске »полностью завершена для PSPACE». Теоретическая информатика. 123 (2): 329–340. Дои:10.1016/0304-3975(94)90131-7.
- ^ а б c Hearn; Демейн (2002). «PSPACE-Полнота головоломок со скользящими блоками и другие проблемы посредством недетерминированной логической модели вычислений с ограничениями». arXiv:cs.CC/0205005.
- ^ А. Кондон, Дж. Фейгенбаум, К. Лунд и П. Шор, Случайные спорщики и трудность аппроксимации стохастических функций, SIAM Журнал по вычислениям 26:2 (1997) 369-400.
- ^ Demaine; Вильетта; Уильямс (2016). «Super Mario Bros. сложнее / проще, чем мы думали». Цитировать журнал требует
| журнал =(помощь) - ^ Гилберт, Ленгауэр и Р. Э. Тарьян: Проблема Пеблинга полна в полиномиальном пространстве. SIAM Journal on Computing, Volume 9, Issue 3, 1980, страницы 513-524.
- ^ Филипп Хертель и Тониан Питасси: Black-White Pebbling завершен для PSPACE В архиве 2011-06-08 на Wayback Machine
- ^ а б Такуми Касаи, Акео Адачи и Сигеки Ивата: Классы Pebble Games и полные задачи, SIAM Journal on Computing, Volume 8, 1979, pages 574-586.
- ^ а б c d е ж грамм час я j k К. Вагнер и Г. Вексунг. Вычислительная сложность. Д. Рейдел Издательство, 1986. ISBN 90-277-2146-7
- ^ а б c Христос Пападимитриу (1985). «Игры против природы». Журнал компьютерных и системных наук. 31 (2): 288–301. Дои:10.1016/0022-0000(85)90045-5.
- ^ А.П. Систла и Эдмунд М. Кларк (1985). «Сложность пропозициональной линейной темпоральной логики». Журнал ACM. 32 (3): 733–749. Дои:10.1145/3828.3837.
- ^ Оценка целочисленной схемы
- ^ Гэри – Джонсон: AL3
- ^ Гэри – Джонсон: AL4
- ^ Галиль, З. Иерархии законченных проблем. В Acta Informatica 6 (1976), 77-88.
- ^ Гэри – Джонсон: AL2
- ^ Л. Дж. Штокмейер и А. Р. Мейер. Проблемы со словами, требующие экспоненциального времени. В материалах 5-го симпозиума по теории вычислений, страницы 1–9, 1973.
- ^ Гэри – Джонсон: AL1
- ^ Дж. Э. Хопкрофт и Дж. Д. Ульман. Введение в теорию автоматов, языки и вычисления, издание первое, 1979.
- ^ а б Д. Козен. Нижние оценки естественных систем доказательства. В Proc. 18-й симпозиум по основам информатики, страницы 254–266, 1977.
- ^ Проблема муравьев Лэнгтона В архиве 2007-09-27 на Wayback Machine, "Обобщенная симметричная проблема муравьев Лэнгтона является PSPACE-полной" Ямагути Эйдзи и Цукиджи Татсуие в Технический отчет IEIC (Институт инженеров электроники, информации и связи )
- ^ Т. Цзян и Б. Равикумар. Минимальные проблемы с NFA - это сложно. SIAM Journal on Computing, 22 (6): 1117–1141, декабрь 1993 г.
- ^ С.-Ю. Курода, "Классы языков и линейно-ограниченные автоматы", Информация и контроль, 7(2): 207–223, июнь 1964 г.
- ^ Регулярное выражение без звезд - это PSPACE-complete
- ^ Гэри – Джонсон: AL12
- ^ Гэри – Джонсон: AL13
- ^ Гэри – Джонсон: AL14
- ^ Гэри-Джонсон: AL16
- ^ Гэри – Джонсон: AL19
- ^ Гэри-Джонсон: AL21
- ^ Антонио Лозано и Хосе Л. Балькасар. Сложность задач графа для лаконично представленных графов. В Манфреде Нагле, редакторе, Теоретико-графические концепции в компьютерных науках, 15-й международный семинар, WG’89, номер 411 в Lecture Notes in Computer Science, стр. 277–286. Springer-Verlag, 1990.
- ^ Дж. Фейгенбаум, С. Каннан, М. Ю. Варди и М. Вишванатан, Сложность задач на графах, представленных как OBDD, Чикагский журнал теоретической информатики, том 5, № 5, 1999.
- ^ C.H. Пападимитриу; М. Яннакакис (1989). «Кратчайшие пути без карты». Конспект лекций по информатике. Proc. 16-й ИКАЛП. 372. Springer-Verlag. С. 610–620.
- ^ Алекс Фабрикант и Христос Пападимитриу. Сложность игровой динамики: BGP-осцилляции, сток-уравнение и не только. В архиве 2008-09-05 на Wayback Machine. В SODA 2008.
- ^ Эрик Д. Демейн и Роберт А. Хирн (23–26 июня 2008 г.). Логика ограничений: унифицированная структура для моделирования вычислений как игр. Материалы 23-й ежегодной конференции IEEE по вычислительной сложности (Complexity 2008). Колледж-Парк, Мэриленд. С. 149–162.
- ^ C.H. Пападимитриу; J.N. Цициклис (1987). «Сложность марковских процессов принятия решений» (PDF). Математика исследования операций. 12 (3): 441–450. Дои:10.1287 / moor.12.3.441. HDL:1721.1/2893.
- ^ I. Chades; Дж. Карвардин; T.G. Мартин; С. Николь; Р. Саббадин; О. Баффет (2012). MOMDP: решение для моделирования проблем адаптивного управления. AAAI'12.
- ^ Казанова Марко А .; и другие. (1984). «Зависимости включения и их взаимодействие с функциональными зависимостями». Журнал компьютерных и системных наук. 28: 29–59. Дои:10.1016/0022-0000(84)90075-8.
- ^ П.В. Гольдберг и C.H. Пападимитриу и Р. Савани (2011). Сложность метода гомотопии, равновесного выбора и решений Лемке – Хаусона. Proc. 52-й FOCS. IEEE. С. 67–76.
- ^ Маартен Маркс (2007). «Сложность модальной логики». В Патрике Блэкберне; Йохан F.A.K. ван Бентем; Фрэнк Уолтер (ред.). Справочник по модальной логике. Эльзевир. п. 170.
- ^ Льюис, Гарри Р. (1978). Сложность разрешимых случаев решения задачи исчисления предикатов. 19-й ежегодный симпозиум по основам информатики. IEEE. С. 35–47.