Clasele L și NL

Acest articol este despre cursurile de limbă pentru o mașină Turing deterministă. Articolul despre utilitarul Unix se numește nl .

Clasa de limbaj L este ansamblul de limbi care sunt decidabile pe o mașină Turing deterministă folosind memorie suplimentară pentru o intrare de lungime n. $O(\log(n))$

Clasa limbilor NL este setul de limbi care sunt determinabile pe o mașină Turing nedeterministă folosind memorie suplimentară pentru o intrare de lungime n. $O(\log(n))$

Exemple:

$\{0^{k}1^{k}:k\geq 0\}\în L$
Fie limbajul un graf direcționat în care există o cale de la s la t , atunci $PATH=\{(G,s,t):G$ $\}$ $PATH\în NL$

NL-probleme complete

Un convertor log-memorie este o mașină Turing cu trei benzi: o bandă de intrare numai pentru citire, o bandă de ieșire doar pentru scriere și o bandă de lucru care nu poate folosi mai mult de celule O(log(n)).

Funcția calculată de un astfel de convertor se numește funcție calculată cu memorie logaritmică .

Problema A reduce logaritmic din memorie la problema B dacă există o funcție logaritmică din memorie care reduce problema A la problema B. Notat $A\leq _{L}B$

O limbă se numește NL-completă dacă aparține NL și orice limbă din NL poate fi redusă la ea logaritmic din memorie.

Teorema:

(A\leq _{L}B)\land (B\in L)\Rightarrow A\in L

Consecinţă:

Dacă un limbaj NL-complet aparține lui L, atunci L = NL

Afirmație:

PATH este o sarcină completă NL.

Consecinţă:

NL\subseteq P

Teorema lui Immermann

clasa conNL — limbi ale căror complemente sunt în NL.

Teorema lui Immermann:

NL=coNL

Literatură

Michael Sipser: „Introducere în teoria calculului”

Clasele de complexitate ale algoritmilor
Considerată ușoară	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-complet ZPP RP BPP BQP EQP APX
Ar trebui să fie dificil	U.P. NP NP complet co-NP co-NP-complet AM M.A._ QMA PH ⊕P PP #P #P IP PSPACE PSPACE-complete
Considerat dificil	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTAR R PR RE RE-completare Co-RE Co-RE-complete TOATE