L (complexitat)

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

En teoria de la complexitat, la classe de complexitat L, també coneguda com a LSPACE o DLOGSPACE, és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing determinista usant una quantitat logarítmica d'espai.[1][2] Formalment, la màquina de Turing te dues cintes, una per codificar l'entrada i només es pot llegir i l'altra cinta té una mida logarítmica però es pot llegir i escriure.

Relacions amb d'altres classes[modifica]

L és una subclasse de NL, que és una classe de llenguatges decidibles en un espai logarítmic en una màquina de Turing no determinista. Un problema a NL es pot transformar en un problema d'accessibilitat en un graf dirigit representant estats i transicions de la màquina no determinista i el límit logarítmic a l'espai implica que aquest graf té un nombre polinòmic de vèrtexs i arestes, del que es dedueix que NL està contingut dins la classe de complexitat P.[3] Per tant es te que

LNLP

i per tant, es te

L també es relaciona amb la classe NC de la següent manera: NC1LNLNC2. En altres paraules, donat un computador paral·lel C amb un nombre de processadors polinòmic O(nk) per una constant k, qualsevol problema que es pot solucionar a C amb un temps O(log n) és de la classe L i qualsevol problema de L es pot solucionar a C en temps O(log n).

Referències[modifica]

  1. Sanjeev., Arora,. Computational complexity : a modern approach. Cambridge: Cambridge University Press, 2009. ISBN 9780521424264. 
  2. H., Papadimitriou, Christos. Computational complexity. Reading, Mass.: Addison-Wesley, 1994. ISBN 0201530821. 
  3. Michael,, Sipser,. Introduction to the theory of computation. Boston: PWS Pub. Co, 1997. ISBN 053494728X.