В теории сложности вычислений , то сложность класса 2-EXPTIME (иногда называют 2-EXP ) является множество всех задач принятия решений разрешимых на детерминированной машине Тьюринга в O (2 2 р ( п ) ) раз, где р ( п ) является полиномиальная функция от n .
Что касается DTIME ,
Мы знаем
2-EXPTIME также можно переформулировать как пространственный класс AEXPSPACE, проблемы, которые могут быть решены с помощью переменной машины Тьюринга в экспоненциальном пространстве. Это один из способов увидеть, что EXPSPACE ⊆ 2-EXPTIME, поскольку переменная машина Тьюринга по крайней мере так же мощна, как детерминированная машина Тьюринга. [1]
2-EXPTIME - это один класс в иерархии классов сложности со все более высокими временными границами. Класс 3-EXPTIME определяется аналогично 2-EXPTIME, но с трехкратным экспоненциальным ограничением по времени . Это можно обобщить на все более высокие временные границы.
2-EXPTIME-завершенные проблемы [ править ]
Обобщения многих полностью наблюдаемых игр полны EXPTIME. Эти игры можно рассматривать как частный пример класса переходных систем, определенных в терминах набора переменных состояния и действий / событий, которые изменяют значения переменных состояния, вместе с вопросом о том, существует ли выигрышная стратегия.
Обобщение этого класса полностью наблюдаемых проблемы частично наблюдаемые проблемы поднимает сложность от EXPTIME -полного к 2-EXPTIME-полному. [2]
См. Также [ править ]
Ссылки [ править ]
- ^ Христос Пападимитриу, Вычислительная сложность (1994), ISBN 978-0-201-53082-7 . Раздел 20.1, следствие 3, стр. 495.
- ^ Юсси Rintanen (2004). «Сложность планирования с частичной наблюдаемостью» (PDF) . Материалы международной конференции по автоматизированному планированию и календарному планированию . AAAI Press: 345–354.
