NL (complexitate)

În informatică teoretică , mai exact în teoria complexității , NL este o clasă de complexitate . Această clasă se mai numește și NLogSpace . Este setul de probleme de decizie care pot fi decise de mașini Turing nedeterministe al căror spațiu de lucru este delimitat de o funcție logaritmică .

Definiție formală

Dacă apelăm , setul de probleme de decizie care pot fi decise de mașinile Turing nedeterministe folosind un spațiu pentru o funcție în mărimea intrării , atunci definim . ${\ mbox {NSPACE}} (t (n))$ $O (t (n))$ $t$ $nu$ ${\ displaystyle {\ mbox {NL}} = {\ mbox {NSPACE}} (jurnal (n))}$

O problemă A este NL-hard dacă orice problemă din NL se reduce la spațiu logaritmic în A. O problemă este NL-completă dacă este în NL și NL-hard.

Exemple de probleme NL-complete

Problema accesibilității (numită și st-accesibilitate) care constă, dat fiind un grafic direcționat G și două vârfuri s și t ale lui G, în determinarea dacă există o cale de la s la t în G, este NL-completă. În această problemă, graficul este reprezentat în mod explicit, cu o matrice de adiacență sau cu liste de adiacență.

Iată alte probleme de decizie NL-complete:

2-SAT , restricționarea problemei SAT (care este NP-completă ) la seturi de clauze cu cel mult două litere .
decideți dacă limbajul unui automat finit nedeterminist este gol.
decideți dacă limbajul unui automat finit determinist (cu un alfabet non-unar) este gol. Dacă alfabetul este unar, problema devine L-completă.
decideți dacă limbajul unui automat finit determinist este limbajul tuturor cuvintelor (aveți grijă, dacă automatul finit este nedeterminist, problema devine PSPACE -completă).
decide dacă limbajul unui automat Büchi este gol este complet NL.

În 1976, Neil D. Jones, Y. Edmund Lien și William T. Laaser au oferit dovezi ale completitudinii NL pentru mai multe probleme, cum ar fi problemele lui Karp pentru completitudinea NP.

Relațiile cu alte clase

Clasa NL este o clasă relativ mică dintre clasele obișnuite. Avem NL P în special . $\ scriptstyle \ subseteq$

În ceea ce privește toate clasele, varianta nedeterministă conține versiunea deterministă, adică L NL . La $\ scriptstyle \ subseteq$ 1 st ianuarie 2015, celălalt mod în care NL L este o problemă deschisă. Un alt rezultat este dat de teorema lui Savitch  : $\ scriptstyle \ subseteq$

Teorema lui Savitch - ${\ mathbf {NL \ subseteq SPACE}} (\ log ^ {2} n)$

Un alt rezultat este teorema datorată lui Neil Immerman și Róbert Szelepcsényi în mod independent:

Teorema Immerman-Szelepcsényi - , pentru orice funcție , în special NL = co-NL ${\ text {NSPACE}} (s (n)) = {\ text {co-NSPACE}} (s (n))$ $s (n) \ geq \ log n$

Clasa NL este inclusă în NC , chiar mai precis în NC 2 . Pentru a demonstra acest lucru, construim un circuit de dimensiune polinomială și adâncime polilogaritmică pentru problema accesibilității care este NL-completă. Arătăm, de asemenea, că clasa NC este stabilă prin reducere logaritmică .

Alte definiții

Definiție prin certificat

O definiție prin certificat este, de asemenea, posibilă, ca și pentru NP . Constrângerile care trebuie adăugate sunt după cum urmează: verificatorul este unidirecțional, adică capul de redare nu se poate întoarce și funcționează în spațiu logaritmic.

Definiția descriptive complexity

În complexitatea descriptivă , NL corespunde logicii de prim ordin cu închidere tranzitivă .

Note și referințe

Sylvain Perifel , algoritmice complexitate , elipse ,2014, 432 p. ( ISBN 9782729886929 , citit online ) , cap. 4.3 („Considerații de bază privind spațiul: comparație cu clasele de timp”), p. 109
„ Examen care pune această întrebare ”
„ Reductibilitatea limitată de spațiu printre problemele combinatorii ”, Journal of Computer and System Sciences , vol. 11, n o 1,1 st august 1975, p. 68-85 ( ISSN 0022-0000 , DOI 10.1016 / S0022-0000 (75) 80050-X , citit on - line , accesat 13 decembrie 2017 )
„ Complexitatea universalității și problemele conexe pentru NFA parțial ordonate ”, Informații și calcul , vol. 255,1 st august 2017, p. 177–192 ( ISSN 0890-5401 , DOI 10.1016 / j.ic.2017.06.004 , citit online , accesat la 13 decembrie 2017 )
Alfred V. Aho și John E. Hopcroft , The Design and Analysis of Computer Algorithms , Addison-Wesley Longman Publishing Co., Inc.,1974( ISBN 0201000296 , citit online )
(în) A. Prasad Sistla Moshe Y. Vardi și Pierre Wolper , " The problem for complementation Buchi automata with applications to temporal logic " , Theoretical Computer Science , vol. 49, n o 21 st ianuarie 1987, p. 217–237 ( ISSN 0304-3975 , DOI 10.1016 / 0304-3975 (87) 90008-9 , citit online , accesat la 7 februarie 2020 ) :
„ Teorema 2.9 Problema nonemptiness pentru automatele Büchi este spațiul de log completat pentru NLOGSPACE. "
(în) Neil D. Jones , Edmund Y. Link și William T. Laaser , „ Probleme noi complete pentru spațiul jurnal nedeterministic ” , Teoria sistemelor matematice , vol. 10, n o 1,Decembrie 1976, p. 1-17 ( ISSN 0025-5661 și 1433-0490 , DOI 10.1007 / bf01683259 , citit online , accesat la 7 noiembrie 2018 )
Sylvain Perifel , algoritmice complexitate , elipse ,2014, 432 p. ( ISBN 9782729886929 , citit online ) , cap. 4.5.2 („Teorema lui Savitch”), p. 118.
Neil. Immerman , „ Spațiul nedeterministic este închis sub complementare ” , SIAM Journal on Computing , vol. 17, n o 5,1 st octombrie 1988, p. 935–938 ( ISSN 0097-5397 , DOI 10.1137 / 0217058 , citit online , accesat la 7 februarie 2020 )
(în) Róbert Szelepcsényi , " Metoda enumerării forțate pentru automatele nedeterministe " , Acta Informatica , vol. 26, n o 3,1 st noiembrie 1988, p. 279–284 ( ISSN 1432-0525 , DOI 10.1007 / BF00299636 , citit online , accesat la 7 februarie 2020 )
(ro) Papadimitriou, Complexitatea calculațională, Teorema 16.1 (p. 395)
Sylvain Perifel , algoritmice complexitate , elipse ,2014, 432 p. ( ISBN 9782729886929 , citit online ) , cap. 4.5.1 („Certificate unidirecționale”), p. 117.
(în) Neil Immerman , „ Limbi care captează clase de complexitate ” , al 15-lea simp STOC ACM. ,1983, p. 347-354 ( citește online ).

Bibliografie

(ro) Sanjeev Arora și Boaz Barak , Computational Complexity: A Modern Approach , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , cap. 4 („Complexitatea spațiului”)

Link extern

(ro) Clasa NL la Complexity Zoo