EXPSPACE - EXPSPACE

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

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

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

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

Что касается DSPACE и NSPACE ,

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

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

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

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

Л. Берман в 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 .
^ Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства» . Технический отчет 62 . Йельский университет.
^ Чарльз Рэкофф (1978). «Проблемы покрытия и ограниченности для систем векторного сложения». Теоретическая информатика : 223-231.
^ Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства» . Технический отчет 62 . Йельский университет.
^ Войцех Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki (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-полным.

[1] Мейер, А.Р. и Л. Стокмейер . Проблема эквивалентности для регулярных выражений с возведением в квадрат требует экспоненциального пространства . 13-й симпозиум IEEE по теории переключений и автоматов , октябрь 1972 г., стр.125–129.

[2] Алур, Раджив; Хенцингер, Томас А. (1994-01-01). «Действительно временная логика». J. ACM . 41 (1): 181–203. DOI : 10.1145 / 174644.174651 . ISSN 0004-5411 .

[3] Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства» . Технический отчет 62 . Йельский университет.

[4] Чарльз Рэкофф (1978). «Проблемы покрытия и ограниченности для систем векторного сложения». Теоретическая информатика : 223-231.

[5] Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства» . Технический отчет 62 . Йельский университет.

[6] Войцех Czerwiński Sławomir Lasota Ranko S Lazić Jérôme Leroux Filip Mazowiecki (2019). «Проблема достижимости сетей Петри не элементарна». STOC 19 .

Languages

In other projects