NE (Complexitat)

En teoria de la complexitat, la classe de complexitat NE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en temps O(kn) per algun k.[1]

Relació amb d'altres classes

[modifica]

Se sap que PNE = NPNE.[2]

Aquesta classe està continguda dins de NEXPTIME.[3]

Referències

[modifica]
  1. ↑ «SIAM (Society for Industrial and Applied Mathematics)». DOI: 10.1137/0201019. [Consulta: 13 desembre 2018].
  2. ↑ «The strong exponential hierarchy collapses» (en anglès). Journal of Computer and System Sciences, 39, 3, 01-12-1989, pàg. 299–322. DOI: 10.1016/0022-0000(89)90025-1. ISSN: 0022-0000.
  3. ↑ «Complexity Zoo:N - Complexity Zoo». Arxivat de l'original el 2017-07-21. [Consulta: 13 desembre 2018].