EXPSPACE

редактировать

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

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

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

Содержание

1 Формально определение
2 Примеры проблем
3 Связь с другими классами
4 См. также
5 Ссылки

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

В терминах DSPACE и NSPACE,

EXPSPACE = ⋃ k ∈ NDSPACE (2 nk) = ⋃ k ∈ NNSPACE (2 nk) {\ displaystyle {\ mathsf {EXPSPACE}} = \ bigcup _ {k \ in \ mathbb {N}} { \ mathsf {DSPACE}} (2 ^ {n ^ {k}}) = \ bigcup _ {k \ in \ mathbb {N}} {\ mathsf {NSPACE}} (2 ^ {n ^ {k}})}

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

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

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

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

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

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

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

Связь с другими классами

EXPSPACE, как известно, является строгим надмножеством PSPACE, NP и P. Также предполагается, что это строгий надмножество EXPTIME, однако это неизвестно.

См. Также

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

Ссылки

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

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