Podwójne problemy wykładnicze?

Question

Czy są jakieś poważne problemy w informatyce, które można rozwiązać tylko w czasie double exponential? A jeśli istnieją, to do której klasy problemów należą?

Answer 1

Od Wikipedia:

W teorii złożoności obliczeniowej, niektóre algorytmy wziąć podwójnie wykładniczy czas:

• Każda procedura decyzyjna dla arytmetyka presburgera provably wymaga co najmniej raz podwójnie wykładniczy

• Obliczanie podstawy Gröbnera na polu. W najgorszym przypadku podstawa Gröbnera może mieć wiele elementów, które są podwójnie wykładnicze w liczbie zmiennych.

• Znalezienie komplet asocjacyjnych-przemienne unifikatorzy

• Zaspokojenie CTL + (co jest w rzeczywistości, 2-EXPTIME-complete)

• kwantyfikatorów eliminacji na prawdziwych zamkniętych obszarach trwa podwójnie wykładniczy czas (patrz Cylindrical algebraic decomposition).

• Obliczanie uzupełnienie wyrażenia regularnego