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
[modifica | modifica wikitesto]- E. Allender e M. Strauss, Measure on small complexity classes with applications for BPP, in Proceedings of IEEE FOCS'94, 1994, pp. 807–818, ECCC TR 94-004, DIMACS TR 94-18.
- R. Book, On languages accepted in polynomial time, in SIAM Journal on Computing, vol. 1, n. 4, 1972, pp. 281–287.
- R. Book, Comparing complexity classes, in Journal of Computer and System Sciences, vol. 3, n. 9, 1974, pp. 213–229.
- R. Impagliazzo e G. Tardos, Decision versus search problems in super-polynomial time, in Proceedings of IEEE FOCS 1989, 1989, pp. 222–227.
- O. Watanabe, Comparison of polynomial time completeness notions, in Theoretical Computer Science, vol. 53, 1987, pp. 249–265.
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Complexity Zoo: Class E Archiviato il 27 agosto 2016 in Internet Archive.