5
Есть ли серьезные проблемы в информатике, которые могут быть решены только в double exponential раз? И если они существуют, то к какому классу проблем они принадлежат?Двойные экспоненциальные проблемы?
A
ответ
8
От Wikipedia:
В теории сложности вычислений, некоторые алгоритмы принимают двойное экспоненциальное время:
Каждой процедура для Пресбургера арифметики доказуемо требует, по меньшей мере, двойного экспоненциального времени
Вычисление базиса Грёбнера над полем. В худшем случае базис Грёбнера может иметь ряд элементов, который вдвое экспоненциальен по числу переменных.
Поиск полный набор ассоциативно-коммутативной объединителей
Удовлетворяя CTL + (что, по сути, 2-EXPTIME-полной)
элиминации кванторов на реальных замкнутых полей занимает дважды экспоненциальный (см. Цилиндрическое алгебраическое разложение).
Расчет дополнения регулярного выражения