E (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 2^O(n).^[1]

És per tant, equivalent a la classe de complexitat DTIME (2^O(n)).^[2]

Referències

1. «SIAM (Society for Industrial and Applied Mathematics)». DOI: 10.1137/0201019. [Consulta: 13 desembre 2018].
2. «Complexity Zoo:E - Complexity Zoo». Arxivat de l'original el 2016-08-27. [Consulta: 13 desembre 2018].