Двойные экспоненциальные проблемы?

Question

Существуют ли какие-либо существенные проблемы в компьютерной науке, которые могут быть решены только в двойном экспоненциальном времени? И если они существуют, то к какому классу проблем они относятся?

Answer 1

Из Википедии:

В теории вычислительной сложности некоторые алгоритмы занимают двойное экспоненциальное время:

• Каждая процедура принятия решения для арифметики Пресбургера доказуемо требует как минимум двойного экспоненциального времени

• Вычисление базиса Гребнера над полем. В наихудшем случае базис Грёбнера может иметь ряд элементов, которые вдвое экспоненциальнее по числу переменных.

• Нахождение полного набора ассоциативно-коммутативных унификаторов

• Удовлетворение CTL+ (которое фактически является 2-EXPTIME-полным)

• Исключение кванторов на вещественных замкнутых полях занимает двукратно экспоненциальное время (см. Цилиндрическое алгебраическое разложение).

• Вычисление дополнения регулярного выражения