E (complessità)
# E (complessità)

Nella teoria della complessità computazionale, la classe di complessità E è l'insieme di problemi decisionali che possono essere risolti da una macchina deterministica di Turing nel tempo 2 ed è perciò uguale alla classe di complessità $DTIME(2^{O(n)}).$

E, diversamente dalla classe simile EXPTIME, non è chiuso sotto le riduzioni molti a uno in tempo polinomiale.

