Оглавление [Скрыть]
2-ВРЕМЯ ИСТЕЧЕНИЯ
-
Определение класса сложности 2-EXPTIME
- Класс 2-EXPTIME включает задачи, решаемые детерминированной машиной Тьюринга за время O(22p(n)), где p(n) – полиномиальная функция.
- 2-EXPTIME также эквивалентен классу AEXPSPACE, где задачи решаются с помощью переменной машины Тьюринга в экспоненциальном пространстве.
-
Иерархия классов сложности
- 2-EXPTIME является одним из классов в иерархии с экспоненциально возрастающими временными рамками, начиная с 3-EXPTIME.
-
Примеры задач в 2-EXPTIME
- Задачи, требующие удвоенного экспоненциального времени, включают арифметику Пресбургера и вычисление базиса Гребнера.
- Алгоритмы, решающие задачи с полным набором ассоциативно-коммутативных объединителей, также требуют удвоенного экспоненциального времени.
- Устранение квантификатора в замкнутых полях и вычисление дополнения к регулярному выражению также являются примерами задач в 2-EXPTIME.
-
Обобщения и расширения
- Задачи с частично наблюдаемыми состояниями повышают сложность с EXPTIME до 2-EXPTIME.
-
Рекомендации и библиография
- Статья содержит ссылки на другие источники и литературу по вычислительной сложности.
Полный текст статьи: