EXPSPACE-полные задачи

В настоящее время я пытаюсь найти полные задачи EXPSPACE (в основном, чтобы найти вдохновение для сокращения), и я удивлен небольшим количеством ожидаемых результатов.

Пока я нашел это, и у меня есть проблемы с расширением списка:

• универсальность (или другие свойства) регулярных выражений с возведением в степень.
• проблемы, связанные с системами сложения векторов
• ненаблюдаемые игры (см., например, этот блог )
• некоторый фрагмент FO-LTL, в О вычислительной сложности разрешимых фрагментов линейной временной логики первого порядка

Знаете ли вы другие контексты, когда EXPSPACE-полнота проявляется естественным образом?

Расширяя пример, указанный Эмилем Джерабеком в комментариях, -полные проблемы естественным образом возникают по всей алгебраической геометрии. Это началось (я думаю) с проблемы идеального членства ( Майр-Мейер и Майр ) и, следовательно, вычисления базисов Грёбнера. Затем это было распространено на вычисление сизигий ( Байер и Стиллман ). Многие естественные проблемы вычислительной алгебраической геометрии оказываются эквивалентными одной из этих проблем. Также см. Обзор Байера – Мамфорда «Что можно вычислить в алгебраической геометрии?»$\mathsf{EXPSPACE}$

Многие проблемы, которые являются PSPACE-полными, становятся EXPSPACE-полными, когда ввод дается «кратко», т. Е. С помощью некоторой кодировки, которая позволяет вам описывать входные данные, которые обычно имеют экспоненциальный размер.

Вот пример для конечных автоматов (эквивалентно для ориентированных графов с помеченными ребрами): решение о том, принимают ли два автомата один и тот же язык (имеют одинаковый набор помеченных путей от источника к узлу назначения), является PSPACE-полным. Если автоматы (графы) задаются булевыми формулами (узлами являются оценки v, v ', .. и существуют булевы формулы, указывающие, является ли va-> v' ребром), задача становится EXPSPACE-полной. NB: есть много других способов краткого определения большого графа / автомата, см., Например, эту статью .

Пример с регулярными выражениями соответствует этому шаблону. Введение нотации ".. ^ 2" для возведения в квадрат позволяет писать компактные регулярные выражения, которые были бы очень большими, если бы вы расширили каждое "(foo) ^ 2" на "foo foo" и "((bar) ^ 2) ^ 2 "by" bar bar bar bar ". Естественно, некоторые задачи, которые являются PSPACE-полными без возведения в квадрат, становятся EXPSPACE-полными с разрешением возведения в квадрат, вот классическая ссылка . [NB: Другие примеры, такие как регулярные выражения с пересечением или дополнением, явно не соответствуют шаблону новой нотации, которая расширяется в экспоненциально больший ввод в стандартной нотации.]

Точно так же задача, полная LOGSPACE (например, достижимость в ориентированных графах), может стать EXPSPACE-полной, если ваша краткая кодировка позволяет описать графы с двойным экспоненциальным размером.

Итог: вы можете легко придумать новые, хотя, возможно, и искусственные, полные EXPSPACE проблемы, рассмотрев классические проблемы PSPACE или LOGSPACE (которых вы найдете много) и допуская компактное / сжатое / .. кодирование ввода.

Временное планирование с одновременными действиями выполняется в EXPSPACE, как показано в

Дж. Ринтанен, «Сложность параллельного временного планирования», Материалы 17-й Международной конференции по автоматизированному планированию и составлению графиков, с. 280–287, 2007 г.

$A$$O$$o=(d,P_s,P_e,P_o,E_s,E_e)$

• $d\in\mathbb{N}$
• $P_s$$P_e$$P_o$$A$
• $E_s$$E_e$$A$

$I$$G$$I$$G$

$d$

Большинство стандартных классов из PSPACE (ну, даже если для NP, если хотите) имеют некоторую проблему листов в качестве полной проблемы. Такие проблемы листов не столь далеки от полных задач естественной машины Тьюринга, но они часто весьма удобны в качестве отправной точки для сокращений. В двух словах, проблема листов дает вам набор разрешенных плиток (то есть: типы плиток, из которых вы можете использовать столько плиток, сколько хотите) и правила их комбинирования, часто с помощью набора H из горизонтально разрешенных пар плитки и набор V вертикально разрешенных типов. Кроме того, первая плитка и последняя плитка могут быть заданы и, в зависимости от фактической версии, и сколько строк и / или столбцов должна иметь плитка. Алгоритмический вопрос состоит в том, существует ли правильная мозаика, то есть назначение позиций мозаикам, это подчиняется всем ограничениям и имеет начальный тайл в левом нижнем положении и последний тайл в верхнем правом положении. (Есть много вариантов относительно точных определений).

Для класса EXPSPACE вы можете выбрать между (как минимум) двумя версиями:

• Экспоненциальная ширина коридора ширины, где задан параметр n, и вопрос заключается в том, существует ли мозаика с 2 ^ n столбцами и любым количеством строк
• Игра на тайлы exp-times-exp, где, при n, размер тайла должен быть 2 ^ n умножен на 2 ^ n, где цель первого игрока - достичь правильного тайлинга, а второй игрок пытается предотвратить это.

Документы, чтобы посмотреть на это - Богдан С. Хлебус: «Игры в Домино-Тайлинг». J. Comput. Сист. Sci. 32 (3): 374-392 (1986) - Питер ван Эмде Боас: «Удобство мозаики», в кн .: Сложность, теория логики и рекурсии, Конспект лекций по чистой и прикладной математике, вып. 187, 1997, с. 331-363.

В разделе «Введение в теорию автоматов, языков и вычислений» Hopcroft / Ullman Thm13.16 приводится пример и доказательство того, что любой недетерминированный алгоритм для теории первого порядка с сложением является NExpTime-hard. поэтому, по-видимому, он также NExpSpace-hard, если какой-то теоретический прорыв не докажет, что его можно решить «в более узком пространстве», но, конечно, этот вопрос похож (почти идентичен?) на L =? P. (Другими словами, все известные проблемы NExpTime-hard также являются основными кандидатами для NExpSpace-hard, и, если это не доказуемо, это, скорее всего, будет означать прорывное решение разделения класса сложности «долго-открытый».) Доказательство исходит от Фишера, Рабина. 1974, "Суперэкспоненциальная сложность пресбургерской арифметики", Сложность вычислений(Р. Карп ред.). Материалы симпозиума SIAM-AMS по прикладной математике.