EXPSPACE - EXPSPACE

В теория сложности вычислений, EXPSPACE это набор из всех проблемы решения разрешимо детерминированным Машина Тьюринга в экспоненциальный Космос, т.е. в ${\displaystyle O(2^{p(n)})}$ пространство, где ${\displaystyle p(n)}$ является полиномиальной функцией от ${\displaystyle n}$. Некоторые авторы ограничивают ${\displaystyle p(n)}$ быть линейная функция, но большинство авторов вместо этого называют получившийся класс ESPACE. Если вместо этого мы воспользуемся недетерминированной машиной, мы получим класс NEXPSPACE, что равно EXPSPACE от Теорема савича.

Проблема решения EXPSPACE-полный если это в EXPSPACE, и каждая проблема в EXPSPACE имеет редукция "много-один" за полиномиальное время к нему. Другими словами, существует полиномиальное время алгоритм который преобразует экземпляры одного в экземпляры другого с тем же ответом. EXPSPACE-полный проблемы можно рассматривать как самые сложные проблемы в EXPSPACE.

EXPSPACE является строгим надмножеством PSPACE, НП, и п и считается строгим надмножеством EXPTIME.

Формальное определение

С точки зрения DSPACE и NSPACE,

${\displaystyle {\mathsf {EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mathsf {NSPACE}}(2^{n^{k}})}$

Примеры проблем

Пример EXPSPACE-полный Проблема заключается в том, чтобы распознать, действительно ли два обычные выражения представляют разные языки, где выражения ограничены четырьмя операторами: объединение, конкатенация, то Клини звезда (ноль или более копий выражения) и возведение в квадрат (две копии выражения).^[1]

Если упустить звезду Клини, тогда проблема станет NEXPTIME -полный, что похоже на EXPTIME-завершено, за исключением того, что это определено в терминах недетерминированные машины Тьюринга а не детерминированный.

Л. Берман в 1980 г. также показал, что проблема проверки / фальсификации любого Первый заказ заявление о действительные числа это включает только дополнение и сравнение (но нет умножение ) в EXPSPACE.

Алур и Хенцингер расширили линейную темпоральную логику с помощью времени (целого числа) и доказали, что проблема достоверности их логики является EXPSPACE-полной.^[2]

Проблема покрываемости для Сети Петри является EXPSPACE-полный.^[3][4] Как известно, проблема достижимости сетей Петри EXPSPACE-жестко надолго,^[5] но оказалось неэлементарным,^[6] так что это доказано не в EXPSPACE.

Отношение к другим классам

EXPSPACE известен как строгий надмножество PSPACE, НП, и п. Кроме того, предполагается, что это строгий надмножество EXPTIME, однако об этом ничего не известно.

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

• Сложность игры

использованная литература

1. Мейер, А. и Л. Штокмейер. Проблема эквивалентности для регулярных выражений с возведением в квадрат требует экспоненциального пространства. 13-й симпозиум IEEE по теории коммутации и автоматов, Октябрь 1972 г., стр.125–129.
2. Алур, Раджив; Хенцингер, Томас А. (1994-01-01). «Действительно временная логика». J. ACM. 41 (1): 181–203. Дои:10.1145/174644.174651. ISSN  0004-5411.
3. Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства». Технический отчет 62. Йельский университет.
4. Чарльз Ракофф (1978). «Проблемы покрытия и ограниченности для систем векторного сложения». Теоретическая информатика: 223--231.
5. Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства». Технический отчет 62. Йельский университет.
6. Войцех Червиньски Славомир Ласота Ранко С. Лазич Жером Леру Филип Мазовецкий (2019). «Проблема достижимости сетей Петри не элементарна». STOC 19.

• Берман, Леонард (1 мая 1980 г.). «Сложность логических теорий». Теоретическая информатика. 11 (1): 71–77. Дои:10.1016/0304-3975(80)90037-7.
• Майкл Сипсер (1997). Введение в теорию вычислений. PWS Publishing. ISBN  0-534-94728-X. Раздел 9.1.1: Экспоненциальная полнота пространства, стр. 313–317. Демонстрирует, что определение эквивалентности регулярных выражений с возведением в степень является EXPSPACE-полным.