L (clasă de complexitate)

În teoria complexității, L (cunoscută și sub numele de LSPACE sau DLOGSPACE) este clasa de complexitate care conține problemele de decizie^⁠(d) care pot fi rezolvate de către o mașină Turing deterministă folosind o un spațiu de memorie^⁠(d) de dimensiuni logaritmice în raport cu intrarea. Formal, mașina Turing are două benzi, dintre care una codifică intrarea și poate fi doar citită, în timp ce cealaltă bandă are dimensiune logaritmică, dar poate fi și citită și scrisă. Spațiul logaritmic este suficient pentru a ocupa un număr constant de pointeri^⁠(d) către intrare și un numărul logaritmic de flaguri booleene, și mulți algoritmi de bază utilizează memoria în acest fel.

Probleme complete și caracterizarea lor logică

Toate problemele netriviale din L sunt complete^⁠(d) în raport cu reducerile în spațiu logaritmic^⁠(d), deci sunt necesare reduceri mai slabe pentru a identifica noțiunile semnificative de L-completitudine, cele mai frecvente fiind reduceri de ordinul întâi^⁠(d).

În 2004, un rezultat al lui Omer Reingold^⁠(d) arată că SL^⁠(d), problema dacă există o cale între două noduri într-un anumit graf neorientat, este în L, demonstrând că L = SL^⁠(d), deoarece USTCON este SL-completă.

O consecință a acestui fapt este o caracterizare logică simplă a lui L: acesta conține exact acele limbaje exprimate în logica de ordinul întâi^⁠(d), cu un operator comutativ suplimentar de închidere tranzitivă^⁠(d) (în termeni de teoria grafurilor, acesta transformă fiecare componentă conexă într-o clică). Acest rezultat are aplicații în limbajele de interogare^⁠(d) a bazelor de date: complexitatea de date a unei interogări este definită ca fiind complexitatea de a răspunde la o interogare fixă având în vedere dimensiunea datelor ca variabilă de intrare. Pentru această măsură, interogări pe bazele de date relaționale^⁠(d) cu informații complete (fără noțiunea de nulluri^⁠(d)), exprimată de exemplu în algebra relațională^⁠(d) sunt în L.

Clase de complexitate asociate

L este o subclasă a lui NL, care este clasa limbajelor decidabile în spațiu logaritmic pe o mașină Turing nedeterministă. O problemă din NL poate fi transformată într-o problemă de accesibilitate^⁠(d) într-un graf orientat reprezentând stări și tranziții de stări ale unei mașini nedeterministe, și limitarea de spațiu logaritmic implică faptul că acest graf are un număr polinomial de noduri și muchii, din care rezultă că NL este conținută în clasa de complexitate P a problemelor rezolvabile în timp determinist polinomial. Astfel L ⊆ NL ⊆ P. Includerea L în P poate fi demonstrată și mai direct: un decident ce folosește spațiu de dimensiune O(log n) nu poate necesita un timp mai mult de 2^{O(log n)} = n^O(1), pentru că acesta este numărul total de configurații posibile.

L se leagă și cu clasa NC în felul următor: NC¹ ⊆ L ⊆ NL ⊆ NC². În cuvinte, considerând un calculator paralel C cu un număr polinomial O(n^k) de procesoare, cu k constant, orice problemă care poate fi rezolvată pe C în O(log n) timp este în L, și orice problemă din L poate fi rezolvată în timp O(log² n) pe C.

Probleme deschise importante sunt dacă L = P, și dacă L = NL.

Clasa asociată a problemelor de funcție^⁠(d) este FL^⁠(d). FL este adesea folosit pentru a defini reduceri logspace^⁠(d).

Proprietăți suplimentare

L este redusă pentru ea însăși, pentru că poate simula interogări în spațiu logaritmic (aproximativ vorbind, „apeluri de funcții care folosesc spațiu logaritmic”), reutilizând același spațiu pentru fiecare interogare.

Alte utilizări

Ideea principală a logspace este că se poate stoca un număr de magnitudine polinomială în logspace și utiliza pentru a reține pointeri la o poziție a intrării.

Clasa logspace este, prin urmare, utilă pentru modelarea calculului unde intrarea este prea mare pentru a încăpea în memoria RAM a unui calculator. Secvențele lungi de ADN și bazele de date sunt bune exemple de probleme unde numai o parte constantă a intrării va fi în memoria RAM la un moment dat și unde sunt pointeri care calculează următoarea parte a intrării de inspectat, folosind astfel doar un spațiu de memorie logaritmic.

Referințe

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. 
• Papadimitriou, Christos (1993). Computational Complexity (ed. 1st). Addison Wesley. ISBN 0-201-53082-1. 
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. 
• Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability^⁠(d). W.H. Freeman. ISBN 0-7167-1045-5.