5
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żą?Podwójne problemy wykładnicze?
A
Odpowiedz
8
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