L (complexitate)

În informatică teoretică , și în special în teoria complexității , clasa L este clasa problemelor de decizie hotărâte de o mașină Turing deterministă care folosește un spațiu de mărime logaritmică în funcție de mărimea intrării. Pentru a fi mai precis, cerința privind spațiul de dimensiuni logaritmice se referă la spațiul utilizabil suplimentar. Se mai notează uneori și LOGSPACE .

Intuitiv, această clasă conține problemele care pot fi hotărâte cu un număr constant de indicatori către celulele de memorie ale intrării problemei și un număr constant de date suplimentare (contoare ale căror valori sunt cuprinse între 0 și o cantitate polinomială în dimensiunea intrării, booleeni etc.).

Definiție formală

Dacă numim ansamblul tuturor problemelor care sunt hotărâte de mașinile Turing deterministe folosind un spațiu (în plus față de intrare) pentru o funcție în mărimea intrării , atunci putem defini L formal prin: $\ mbox {SPACE} (t (n))$ $O (t (n))$ $t$ $nu$

${\ mbox {L}} = {\ mbox {SPACE}} (\ log (n)) \.$

Exemple de probleme

Exemple de limbi

Limbajul este în L . Iată un algoritm care decide în spațiul logaritmic: ${\ displaystyle \ {0 ^ {k} 1 ^ {k} \ mid k \ in \ mathbb {N} \}}$ ${\ displaystyle \ {0 ^ {k} 1 ^ {k} \ mid k \ in \ mathbb {N} \}}$

procedure M(w) si w vide accepter i = 0 tant que w[i] == 0 i := i+1 compteurzero := i tant que w[i] == 1 i := i+1 si w[i] != ' ' (différent de la fin de mot) refuser si compteurzero == (i - compteurzero) accepter sinon refuser

Cuvântul w nu este modificat: este intrarea și nu se ia în calcul în memoria utilizată. Numărăm doar memoria suplimentară, și anume variabilele i și contrazero care sunt numere întregi pozitive mărginite de | w | și că putem codifica în spațiul logaritmic în | w |.

Limbajul cuvintelor generat de următoarea gramatică algebrică este în L: S -> (S) | SS | ε.

Multiplicare

Reprezentarea binară a întregului este notată în această secțiune. Limbajul este în L . Următorul algoritm recunoaște utilizarea unui spațiu în , unde este dimensiunea intrării sale. Algoritmul ia ca intrare trei numere întregi n , m și p verifică dacă multiplicarea lui n cu m este într-adevăr p . Se calculeaza la fiecare iterație i - lea bit al rezultatului înmulțirii și o compară cu i - lea bit p. $nu$ ${\ displaystyle \ langle n \ rangle}$ ${\ displaystyle \ mathrm {MULT} = \ left \ {(\ langle n \ rangle, \ langle m \ rangle, \ langle n \ times m \ rangle) \ mid n, m \ in \ mathbb {N} \ right \ }}$ ${\ displaystyle \ mathrm {MULT}}$ ${\ displaystyle {\ mathcal {O}} (\ log T)}$ $T$

Următoarele proceduri sunt utilizate în descrierea algoritmului:

increment ( x ), crește variabila x ;
est_un ( x , i ), indică dacă i - lea bit de x este nenulă, dacă i este mai mare decât dimensiunea x bit este considerat a fi zero;
divide_by_two ( x ), înlocuiește x cu coeficientul diviziunii sale euclidiene cu 2; acest lucru poate fi implementat ca o schimbare de biți a x de la unul la cei mai puțin semnificativi biți.

procedure verifierMultiplication(n, m, p) retenue = 0 i = 0 tant que i < max(|n| + |m| - 1, |p|) j = 0 tant que j < i k = 0 tant que k + j <= i si est_un(n, j) et est_un(m, k) incrémenter(retenue) k := k + 1 si p[i] != retenue[0] rejeter diviser_par_deux(retenue) j := j + 1 i := i + 1 accepter

Valoarea contoarelor i , j și k utilizate nu depășește dimensiunea intrării și, prin urmare, poate fi codificată logaritmic în dimensiunea intrării. Procedurile și comparațiile introduse utilizează cel mult un spațiu logaritmic în mărimea intrării. În cele din urmă, valoarea variabilei selectate nu poate depăși , deci poate fi codificată pe un spațiu din . ${\ displaystyle \ max \ left (| n | + | m | -1, | p | \ right) ^ {3} <T ^ {3}}$ ${\ displaystyle {\ mathcal {O}} \ left (3 \ log T \ right)}$

Relații cu alte clase de complexitate

Știm următoarele incluziuni:

NC 1 ⊆ L ⊆ NL ⊆ AC 1 ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE

Se știe, de asemenea, că includerea L în PSPACE este strictă, deci una dintre incluziunile de mai sus este strictă. Nu este imposibil ca toți să fie .

Clasa SL și problema de accesibilitate într-un grafic nedirecționat

Lewis și Christos Papadimitriou au definit în 1982 varianta „simetrică” a lui L: clasa SL (pentru spațiul jurnal simetric în engleză). Definiția originală folosește noțiunea de mașină de Turing simetrică în locul mașinilor de Turing deterministe clasice. În mod echivalent, SL este clasa de probleme decisă de o mașină Turing nedeterministă în spațiul logaritmic, cu următoarea constrângere de simetrie:

Dacă mașina poate trece de la configurația A la configurația B, atunci mașina poate trece și de la configurația B la configurația A.

Astfel, clasa SL este între L și NL . Lewis și Papadimitriou au arătat că problema de accesibilitate într-un grafic nedirecționat este completă SL (pentru reduceri logaritmice ). Această problemă de accesibilitate ia ca intrare un grafic nedirecționat, un vârf s și un vârf t și determină dacă există o cale de la un vârf dat s la un vârf dat t (rețineți că versiunea problemei de accesibilitate pentru graficele orientate este NL-completă ).

În 2004, Omer Reingold arată că problema accesibilității într-un grafic neorientat este decisă în spațiul logaritmic pe o mașină deterministă și, prin urmare, că L = SL . Dovada lui Reingold folosește noțiunea de grafice de expansiune . Acest rezultat i-a adus premiul Gödel în 2009.

Note și referințe

Garey și Johnson 1979 , p. 177 .
Sipser 1997 , definiție 8.12, p. 295 .
Michael Sipser , Introducere în teoria calculației , Editura Internațională Thomson,1 st decembrie 1996, 396 p. ( ISBN 0-534-94728-X , citit online ) , p. 349, Exemplul 8.18
(în) Dexter C. Kozen, Theory of Computation , Homework 3. Ex. 1. p. 277
Michael Sipser , Introducere în teoria calculației , Editura Internațională Thomson,1 st decembrie 1996, 396 p. ( ISBN 0-534-94728-X , citit online ) , p. 359, Ex. 8.20
Omer Reingold , Salil Vadhan și Avi Wigderson , „ Undele de entropie, produsul cu grafice în zig-zag și noii expansori cu grad constant ”, Annals of Mathematics , vol. 155, n o 1,2002, p. 157–187 ( DOI 10.2307 / 3062153 , JSTOR 3062153 , Math Reviews 1888797 , citiți online )
Omer Reingold , „ Conectivitate nedirecționată în spațiul jurnal ” , Jurnalul ACM , vol. 55, nr . 4,2008, p. 1–24 ( citiți online )

Bibliografie

(ro) Sanjeev Arora și Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , cap. 1 („Modelul de calcul - și de ce nu contează”)
Omer Reingold , „ Conectivitate ST nedirecționată în spațiul jurnal ”, Colocviu electronic despre complexitatea computațională , nr . 94,2004( citește online ). Versiune electronica.
Omer Reingold , „ Conectivitate nedirecționată în spațiul jurnal ”, Jurnalul ACM , vol. 55, nr . 4,2008, p. 1–24 ( DOI 10.1145 / 1391289.1391291 , Recenzii matematice 2445014 ). Versiunea jurnalului.
(ro) MR Garey și DS Johnson , Computers and intractability: a guide to theory of NP-completeeness , New York, WH Freeman,1979, 338 p. ( ISBN 0-7167-1045-5 ) , Secțiunea 7.5: Spațiul logaritmic, pp. 177–181
(ro) Christos Papadimitriou , Complexitate computațională , citire (masă), Addison Wesley,1993, Prima ed. , 523 p. ( ISBN 0-201-53082-1 ) , p. Capitolul 16: Spațiul logaritmic, pp. 395-408
(ro) Michael Sipser , Introducere în teoria calculelor , PWS Publishing,1997, 396 p. ( ISBN 0-534-94728-X ) , Secțiunea 8.4: Clasele L și NL, pp. 294–296

linkuri externe