Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В теории сложности вычислений , EXPSPACE это совокупность всех задач принятия решений разрешимых детерминированной машиной Тьюринга в экспоненциальном пространстве , то есть в пространстве, где есть полиномиальная функция . Некоторые авторы ограничивают быть линейной функцией , но большинство авторов вместо называть получившийся класс ESPACE . Если вместо этого мы воспользуемся недетерминированной машиной, мы получим класс NEXPSPACE , который равен EXPSPACE по теореме Савича .

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

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

Формальное определение [ править ]

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

Примеры проблем [ править ]

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

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

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

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

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

Отношение к другим классам [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ Мейер, AR и Л. Стокмейер . Проблема эквивалентности для регулярных выражений с возведением в квадрат требует экспоненциального пространства . 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). «Проблемы покрытия и ограниченности для систем векторного сложения». Теоретическая информатика : 22–31.
  5. ^ Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства» . Технический отчет 62 . Йельский университет.
  6. ^ Войцех 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-полным.