2-EXPTIME

Оглавление1 2-ВРЕМЯ ИСТЕЧЕНИЯ1.1 Определение класса сложности 2-EXPTIME1.2 Иерархия классов сложности1.3 Примеры задач в 2-EXPTIME1.4 Обобщения и расширения1.5 Рекомендации и библиография2 […]

2-ВРЕМЯ ИСТЕЧЕНИЯ

  • Определение класса сложности 2-EXPTIME

    • Класс 2-EXPTIME включает задачи, решаемые детерминированной машиной Тьюринга за время O(22p(n)), где p(n) – полиномиальная функция. 
    • 2-EXPTIME также эквивалентен классу AEXPSPACE, где задачи решаются с помощью переменной машины Тьюринга в экспоненциальном пространстве. 
  • Иерархия классов сложности

    • 2-EXPTIME является одним из классов в иерархии с экспоненциально возрастающими временными рамками, начиная с 3-EXPTIME. 
  • Примеры задач в 2-EXPTIME

    • Задачи, требующие удвоенного экспоненциального времени, включают арифметику Пресбургера и вычисление базиса Гребнера. 
    • Алгоритмы, решающие задачи с полным набором ассоциативно-коммутативных объединителей, также требуют удвоенного экспоненциального времени. 
    • Устранение квантификатора в замкнутых полях и вычисление дополнения к регулярному выражению также являются примерами задач в 2-EXPTIME. 
  • Обобщения и расширения

    • Задачи с частично наблюдаемыми состояниями повышают сложность с EXPTIME до 2-EXPTIME. 
  • Рекомендации и библиография

    • Статья содержит ссылки на другие источники и литературу по вычислительной сложности. 

Полный текст статьи:

2-EXPTIME — Википедия

Оставьте комментарий

Прокрутить вверх