Třídy L a NL

Tento článek je o jazykových třídách pro deterministický Turingův stroj. Článek o unixovém nástroji se nazývá nl .

Jazyková třída L je množina jazyků, které jsou rozhoditelné na deterministickém Turingově stroji pomocí dodatečné paměti pro vstup délky n. $O(\log(n))$

Třída jazyků NL je množina jazyků, které jsou rozhoditelné na nedeterministickém Turingově stroji pomocí dodatečné paměti pro vstup délky n. $O(\log(n))$

Příklady:

$\{0^{k}1^{k}:k\geq 0\}\v L$
Nechť jazyk je orientovaný graf , ve kterém je cesta od s do t $CESTA=\{(G,s,t):G$ $\}$ $PATH\v NL$

Úplné problémy NL

Převodník paměti log je Turingův stroj se třemi páskami: vstupní páskou pouze pro čtení, výstupní páskou pouze pro zápis a pracovní páskou, která nemůže používat více než O(log(n)) buňky.

Funkce vypočítaná takovým převodníkem se nazývá funkce vypočítaná s logaritmickou pamětí .

Problém A redukuje logaritmicky z paměti na problém B , pokud existuje logaritmická funkce z paměti, která redukuje problém A na problém B. Označeno $A\leq _{L}B$

Jazyk se nazývá NL-complete , pokud patří do NL a kterýkoli jazyk v NL na něj lze logaritmicky redukovat z paměti.

Teorém:

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

Následek:

Jestliže NL-úplný jazyk patří do L, pak L = NL

Tvrzení:

PATH je NL-úplný úkol.

Následek:

NL\subseteq P

Immermannova věta

class coNL — jazyky, jejichž doplňky jsou v NL.

Immermannova věta:

NL=coNL

Literatura

Michael Sipser: „Úvod do teorie počítání“

Třídy složitosti algoritmů
Považováno za světlo	DLOGTIME AC 0 ACC 0 TC0 [ en L SL RL NL NC SC CC P P-kompletní ZPP RP BPP BQP EQP APX
Prý to bude těžké	U.P. NP NP kompletní co-NP co-NP-kompletní AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-complete
Považováno za obtížné	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete VŠECHNY