E (Complexitat)
Classe de complexitat
En teoria de la complexitat, la classe de complexitat E és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps 2O(n).[1]
És per tant, equivalent a la classe de complexitat DTIME (2O(n)).[2]
Referències
modifica- ↑ «SIAM (Society for Industrial and Applied Mathematics)». DOI: 10.1137/0201019. [Consulta: 13 desembre 2018].
- ↑ «Complexity Zoo:E - Complexity Zoo». Arxivat de l'original el 2016-08-27. [Consulta: 13 desembre 2018].