2-ВРЕМЯ ЭКСПЛУАТАЦИИ
В теории сложности вычислений класс сложности 2-EXPTIME (иногда называемый 2-EXP ) — это набор всех задач решения , решаемых детерминированной машиной Тьюринга за O (2 2 п ( п ) ) время, где p ( n ) — полиномиальная функция от n .
Что касается DTIME ,
Мы знаем
2-EXPTIME также можно переформулировать как пространственный класс AEXPSPACE — проблемы, которые можно решить с помощью попеременной машины Тьюринга в экспоненциальном пространстве. Это один из способов убедиться в том, что EXPSPACE ⊆ 2-EXPTIME, поскольку попеременная машина Тьюринга по крайней мере столь же мощна, как и детерминированная машина Тьюринга. [1]
2-EXPTIME — это один класс в иерархии классов сложности с все более высокими временными ограничениями. Класс 3-EXPTIME определяется аналогично 2-EXPTIME, но с тройным экспоненциальным ограничением времени. . Это можно обобщить на все более и более высокие временные рамки.
Примеры [ править ]
Примеры алгоритмов, требующих как минимум 2-EXPTIME, включают:
- Доказуемо, что каждая процедура решения арифметики Пресбургера требует как минимум удвоенного экспоненциального времени. [2]
- Вычисление базиса Грёбнера над полем. В худшем случае базис Грёбнера может иметь число элементов, дважды экспоненциальное по числу переменных. С другой стороны, сложность базисных алгоритмов Грёбнера в наихудшем случае вдвойне экспоненциальна как по количеству переменных, так и по размеру записи. [3]
- Нахождение полного набора ассоциативно-коммутативных унификаторов [4]
- Удовлетворительный CTL + (который, по сути, является 2-EXPTIME-полным) [5]
- Устранение кванторов в реальных замкнутых полях занимает дважды экспоненциальное время (см. Цилиндрическое алгебраическое разложение ).
- Вычисление дополнения к регулярному выражению [6]
Проблемы 2-EXPTIME-complete [ править ]
Обобщения многих полностью наблюдаемых игр EXPTIME-полны. Эти игры можно рассматривать как частные случаи класса переходных систем, определенных в терминах набора переменных состояния и действий/событий, которые изменяют значения переменных состояния, а также вопроса о том, существует ли выигрышная стратегия . Обобщение этого класса полностью наблюдаемых задач до частично наблюдаемых задач повышает сложность с EXPTIME -полных до 2-EXPTIME-полных. [7]
См. также [ править ]
Ссылки [ править ]
- ^ Христос Пападимитриу , Вычислительная сложность (1994), ISBN 978-0-201-53082-7 . Раздел 20.1, следствие 3, стр. 495.
- ^ Фишер, М.Дж. и Майкл О. Рабин , 1974, « Суперэкспоненциальная сложность арифметики Пресбургера. Архивировано 15 сентября 2006 г. в Wayback Machine « Материалы симпозиума SIAM-AMS по прикладной математике, том 7 : 27–41» .
- ^ Дюбе, Томас В. (август 1990 г.). «Структура полиномиальных идеалов и базисов Грёбнера». SIAM Journal по вычислительной технике . 19 (4): 750–773. дои : 10.1137/0219053 .
- ^ Капур, Дипак; Нарендран, Палиат (1992), «Двойная экспоненциальная сложность вычисления полного набора AC-объединителей», [1992] Труды седьмого ежегодного симпозиума IEEE по логике в информатике , стр. 11–21, doi : 10.1109/LICS .1992.185515 , ISBN 0-8186-2735-2 , S2CID 206437926 .
- ^ Йохансен, Ян; Ланге, Мартин (2003), "CTL + является полным для двойного экспоненциального времени», в Бэтене, Йосе К.М.; Ленстра, Ян Карел ; Пэрроу, Иоахим; Вегингер, Герхард Дж. (ред.), Труды 30-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2003) ( PDF) , Конспекты лекций по информатике, том 2719, Springer-Verlag, стр. 767–775, doi : 10.1007/3-540-45061-0_60 , ISBN. 978-3-540-40493-4 , заархивировано из оригинала (PDF) 30 сентября 2007 г. , получено 22 декабря 2006 г.
- ^ Грубер, Герман; Хольцер, Маркус (2008). «Конечные автоматы, связность орграфов и размер регулярного выражения» (PDF) . Материалы 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2008) . Том. 5126. стр. 39–50. дои : 10.1007/978-3-540-70583-3_4 .
- ^ Юсси Ринтанен (2004). «Сложность планирования с частичной наблюдаемостью» (PDF) . Материалы международной конференции по автоматизированному планированию и составлению графиков . АААИ Пресс: 345–354.