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
  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].