Vés al contingut

E (Complexitat)

De la Viquipèdia, l'enciclopèdia lliure

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].
Obtingut de «https://ca.wikipedia.org/w/index.php?title=E_(Complexitat)&oldid=27782777»