EXPSPACE
В сложности вычислений теории EXPSPACE — это набор всех задач решения , решаемых детерминированной машиной Тьюринга в экспоненциальном пространстве , т. е. в пространство, где является полиномиальной функцией от . Некоторые авторы ограничивают быть линейной функцией , но большинство авторов вместо этого называют полученный класс ESPACE . Если вместо этого мы воспользуемся недетерминированной машиной, мы получим класс NEXPSPACE равен EXPSPACE , который по теореме Савича .
Задача решения является EXPSPACE-полной, если она находится в EXPSPACE , и каждая проблема в EXPSPACE имеет полиномиальное сведение к ней «много-один». Другими словами, существует алгоритм с полиномиальным временем , который преобразует экземпляры одного в экземпляры другого с тем же ответом. Задачи , полные EXPSPACE, можно считать самыми сложными задачами в EXPSPACE .
EXPSPACE является строгим расширенным набором PSPACE , NP и P и считается строгим расширенным набором EXPTIME .
Формальное определение [ править ]
Что касается DSPACE и NSPACE ,
Примеры проблем [ править ]
Примером EXPSPACE-полной проблемы является проблема распознавания того, представляют ли два регулярных выражения разные языки, где выражения ограничены четырьмя операторами: объединение, конкатенация , звезда Клини (ноль или более копий выражения) и возведение в квадрат ( две копии выражения). [1]
Алур и Хенцингер расширили линейную темпоральную логику с помощью времен (целых чисел) и доказали, что проблема достоверности их логики является EXPSPACE-полной. [2]
Проблема покрываемости сетей Петри является EXPSPACE -полной. [3]
Проблема достижимости была EXPSPACE -трудной. сетей Петри долгое время [4] но показано, что это неэлементарно , [5] так что, вероятно, не в EXPSPACE . В 2022 году было показано, что он является полным по Аккерману . [6] [7]
Отношения с другими классами [ править ]
EXPSPACE является строгим расширенным набором PSPACE , NP и P. , как известно , Предполагается, что это строгий расширенный набор EXPTIME , однако это неизвестно.
См. также [ править ]
Ссылки [ править ]
- ^ Мейер, А.Р. и Л. Стокмейер . Проблема эквивалентности регулярных выражений с возведением в квадрат требует экспоненциального пространства . 13-й симпозиум IEEE по теории коммутации и автоматов , октябрь 1972 г., стр. 125–129.
- ^ Алур, Раджив; Хензингер, Томас А. (1 января 1994 г.). «Действительно временная логика» . Дж. АКМ . 41 (1): 181–203. дои : 10.1145/174644.174651 . ISSN 0004-5411 .
- ^ Чарльз Ракофф (1978). «Задачи покрытия и ограниченности систем сложения векторов». Теоретическая информатика : 223–231.
- ^ Липтон, Р. (1976). «Проблема достижимости требует экспоненциального пространства» . Технический отчет 62 . Йельский университет.
- ^ Войцех Червинский Славомир Ласота Ранко S LaOŚCI Жером Леру Филип Мазовецкий (2019). «Проблема достижимости сетей Петри не элементарна». СТОК 19 .
- ^ Леру, Жером (февраль 2022 г.). «Проблема достижимости сетей Петри не является примитивно-рекурсивной» . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2021 г. IEEE. стр. 1241–1252. arXiv : 2104.12695 . дои : 10.1109/FOCS52979.2021.00121 . ISBN 978-1-6654-2055-6 .
- ^ Брубейкер, Бен (4 декабря 2023 г.). «Просто кажущаяся проблема дает числа, слишком большие для нашей Вселенной» . Журнал Кванта .
- Берман, Леонард (1 мая 1980 г.). «Сложность логических теорий» . Теоретическая информатика . 11 (1): 71–77. дои : 10.1016/0304-3975(80)90037-7 .
- Майкл Сипсер (1997). Введение в теорию вычислений . Издательство ПВС. ISBN 0-534-94728-Х . Раздел 9.1.1: Экспоненциальная полнота пространства, стр. 313–317. Демонстрирует, что определение эквивалентности регулярных выражений с возведением в степень является EXPSPACE-полным.