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 2O(n) ed è perciò uguale alla classe di complessità DTIME(2O(n)).
E, diversamente dalla classe simile EXPTIME, non è chiuso sotto le riduzioni molti a uno in tempo polinomiale.
Bibliografia
Collegamenti esterni Complexity Zoo: Class E
Categoria:Classi di complessità