5
Ci sono problemi significativi nell'informatica che possono essere risolti solo nel tempo double exponential? E se esistono allora a quale classe di problemi appartengono?Doppi problemi esponenziali?
A
risposta
8
Da Wikipedia:
Nella teoria della complessità computazionale, alcuni algoritmi richiedono tempo doppio esponenziale:
Ogni procedura di decisione per Presburger richiede dimostrabilmente almeno tempo doppio esponenziale
Calcolare una base di Gröbner su un campo. Nel caso peggiore, una base di Gröbner può avere un numero di elementi che è doppiamente esponenziale nel numero di variabili.
Trovare un set completo di riunificatori associativi commutativa
Soddisfacente CTL + (che è, in effetti, 2-EXPTIME-completo)
eliminazione Quantifier sui campi chiusi reali prende un doppiamente esponenziale tempo (vedi Decomposizione algebrica cilindrica).
Calcolando il complemento di un'espressione regolare