E (Complexitat)

De Viquipèdia
Salta a la navegació Salta a la cerca

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