2-ЭКСПТАЙМ

В теории сложности вычислений класс сложности 2-EXPTIME (иногда называемый 2-EXP ) представляет собой множество всех задач принятия решений , решаемых детерминированной машиной Тьюринга за время O (2 ^{2 ^{p ( n )}} ), где p ( n ) — полиномиальная функция от n .

С точки зрения DTIME ,

{\mathsf {2{\mbox{-}}EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{2^{n^{k}}}\right).

Мы знаем

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE ⊆ 2-EXPTIME ⊆ ЭЛЕМЕНТАРНЫЙ .

2-EXPTIME также можно переформулировать как класс пространства AEXPSPACE, проблемы, которые могут быть решены с помощью чередующейся машины Тьюринга в экспоненциальном пространстве. Это один из способов увидеть, что EXPSPACE ⊆ 2-EXPTIME, поскольку чередующаяся машина Тьюринга по крайней мере столь же мощна, как и детерминированная машина Тьюринга. ^[1]

2-EXPTIME — это один класс в иерархии классов сложности с возрастающими временными границами. Класс 3-EXPTIME определяется аналогично 2-EXPTIME, но с трижды экспоненциальной временной границей . Это можно обобщить на все более высокие временные границы. $2^{2^{2^{n^{k}}}}$

Примеры

Примеры алгоритмов, требующих как минимум 2-EXPTIME, включают:

Каждая процедура принятия решения для арифметики Пресбургера доказуемо требует по крайней мере в два раза большее экспоненциальное время ^[2]
Вычисление базиса Грёбнера над полем. В худшем случае базис Грёбнера может иметь число элементов, которое дважды экспоненциально по числу переменных. С другой стороны, сложность алгоритмов базиса Грёбнера в худшем случае дважды экспоненциальна по числу переменных, а также по размеру записи. ^[3]
Нахождение полного набора ассоциативно-коммутативных унификаторов ^[4]
Удовлетворение CTL ⁺ (что, по сути, 2-EXPTIME-complete) ^[5]
Устранение кванторов в вещественных замкнутых полях занимает дважды экспоненциальное время (см. Цилиндрическое алгебраическое разложение ).
Вычисление дополнения регулярного выражения ^[6]

2-EXPTIME-полные проблемы

Обобщения многих полностью наблюдаемых игр являются 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 по вычислениям . 19 (4): 750–773 . doi :10.1137/0219053.
^ Капур, Дипак; Нарендран, Палиат (1992), «Двойная экспоненциальная сложность вычисления полного набора AC-унификаторов», [1992] Труды седьмого ежегодного симпозиума IEEE по логике в компьютерных науках, стр. 11–21 , doi :10.1109/LICS.1992.185515, ISBN 0-8186-2735-2, S2CID 206437926.
^ Йохансен, Ян; Ланге, Мартин (2003), «CTL ⁺ is complete for double exponential time», в Baeten, Jos CM; Lenstra, Jan Karel ; Parrow, Joachim; Woeginger, Gerhard J. (ред.), Труды 30-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2003) (PDF) , Lecture Notes in Computer Science, т. 2719, Springer-Verlag, стр. 767– 775, doi :10.1007/3-540-45061-0_60, ISBN 978-3-540-40493-4, заархивировано из оригинала (PDF) 2007-09-30 , извлечено 2006-12-22.
^ Грубер, Герман; Хольцер, Маркус (2008). «Конечные автоматы, связность диграфов и размер регулярных выражений» (PDF) . Труды 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2008) . Том 5126. С. 39–50. doi : 10.1007/978-3-540-70583-3_4.
^ Юсси Ринтанен (2004). «Сложность планирования с частичной наблюдаемостью» (PDF) . Труды Международной конференции по автоматизированному планированию и составлению расписаний . AAAI Press: 345–354 .

[1] Христос Пападимитриу , Вычислительная сложность (1994), ISBN 978-0-201-53082-7 . Раздел 20.1, следствие 3, стр. 495.

[2] Фишер, М. Дж . и Майкл О. Рабин , 1974, ""Суперэкспоненциальная сложность арифметики Пресбургера. Архивировано 15 сентября 2006 г. в Wayback Machine " Труды симпозиума SIAM-AMS по прикладной математике, том 7 : 27–41

[3] Дубе, Томас В. (август 1990 г.). «Структура полиномиальных идеалов и базисов Грёбнера». Журнал SIAM по вычислениям . 19 (4): 750–773 . doi :10.1137/0219053.

[4] Капур, Дипак; Нарендран, Палиат (1992), «Двойная экспоненциальная сложность вычисления полного набора AC-унификаторов», [1992] Труды седьмого ежегодного симпозиума IEEE по логике в компьютерных науках, стр. 11–21 , doi :10.1109/LICS.1992.185515, ISBN 0-8186-2735-2, S2CID 206437926.

[5] Йохансен, Ян; Ланге, Мартин (2003), «CTL ⁺ is complete for double exponential time», в Baeten, Jos CM; Lenstra, Jan Karel ; Parrow, Joachim; Woeginger, Gerhard J. (ред.), Труды 30-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2003) (PDF) , Lecture Notes in Computer Science, т. 2719, Springer-Verlag, стр. 767– 775, doi :10.1007/3-540-45061-0_60, ISBN 978-3-540-40493-4, заархивировано из оригинала (PDF) 2007-09-30 , извлечено 2006-12-22.

[6] Грубер, Герман; Хольцер, Маркус (2008). «Конечные автоматы, связность диграфов и размер регулярных выражений» (PDF) . Труды 35-го Международного коллоквиума по автоматам, языкам и программированию (ICALP 2008) . Том 5126. С. 39–50. doi : 10.1007/978-3-540-70583-3_4.

[7] Юсси Ринтанен (2004). «Сложность планирования с частичной наблюдаемостью» (PDF) . Труды Международной конференции по автоматизированному планированию и составлению расписаний . AAAI Press: 345–354 .