NL (Complexitat)

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

En teoria de la complexitat, la classe de complexitat NL és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista usant una quantitat logarítmica d'espai.[1][2]

NL és una generalització de la classe L. Ja que tota màquina de Turing determinista és també una màquina de Turing no determinsita, L està dins de NL.

NL es pot definir en termes de recursos com NL = NSPACE(log n).

Relacions amb d'altres classes[modifica]

Es coneix que NL està dins de P, però no se sap si NL = P o bé L = NL. Se sap que NL = co-NL, la classe dels llenguatges que els seus complements son a NL. També es coneix que

I per tant,

Més precisament, NL està dins de la classe AC1. S'ha demostrat que NL és igual a ZPL, tot i que no se sap si és igual a RPL o ZPLP.

Pel teorema de Savitch s'obté directament que

Referències[modifica]

  1. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  2. H., Papadimitriou, Christos. Computational complexity. Reading, Mass.: Addison-Wesley, 1994. ISBN 0201530821.