Doppelte exponentielle Probleme?

Question

Gibt es signifikante Probleme in der Informatik, die nur in double exponential Zeit gelöst werden können? Und wenn sie existieren, zu welcher Klasse von Problemen gehören sie?

Answer 1

Von Wikipedia:

In Komplexitätstheorie, nehmen einige Algorithmen doppelt exponentielle Zeit:

• Jede Entscheidungsverfahren für Presburger Arithmetik beweisbar mindestens doppelt exponentielle Zeit benötigt

• Berechnen einer Gröbner-Basis über ein Feld. Im schlimmsten Fall kann eine Gröbner-Basis eine Anzahl von Elementen aufweisen, die in der Anzahl der Variablen doppelt exponentiell ist.

• einen kompletten Satz von assoziativ-kommutative Unifikatoren Finding

• Satisfying CTL + (das ist in der Tat, 2-EXPTIME-complete)

• Quantorenelimination auf realen geschlossenen Feldern nimmt ein doppelt exponentiellen Zeit (siehe Zylindrische algebraische Zerlegung).

• Berechnung der Ergänzung eines regulären Ausdrucks