Klasserna L och NL

Den här artikeln handlar om språkklasser för en deterministisk Turing-maskin. Artikeln om unix-verktyget heter nl .

Språkklassen L är uppsättningen språk som kan avgöras på en deterministisk Turing-maskin som använder extra minne för en inmatning med längden n. $O(\log(n))$

Klassen av NL-språk är uppsättningen språk som kan avgöras på en icke -deterministisk Turing-maskin som använder extra minne för en inmatning med längden n. $O(\log(n))$

Exempel:

$\{0^{k}1^{k}:k\geq 0\}\i L$
Låt språket vara en riktad graf där det finns en väg från s till t , då $PATH=\{(G,s,t):G$ $\}$ $PATH\i NL$

NL-fullständiga problem

En log-minnesomvandlare är en Turing-maskin med tre band: ett skrivskyddat inmatningsband, ett skrivskyddat utmatningsband och ett arbetsband som inte kan använda mer än O(log(n))-celler.

Funktionen som beräknas av en sådan omvandlare kallas en funktion som beräknas med logaritmiskt minne .

Problem A reducerar logaritmiskt från minne till problem B om det finns en funktion logaritmiskt från minne som reducerar problem A till problem B. Betecknas $A\leq _{L}B$

Ett språk kallas NL-komplett om det tillhör NL och vilket språk som helst i NL kan reduceras till det logaritmiskt från minnet.

Sats:

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

Följd:

Om ett NL-komplett språk tillhör L, då L = NL

Påstående:

PATH är en NL-fullständig uppgift.

Följd:

NL\subseteq P

Immermanns teorem

klass coNL — språk vars komplement är i NL.

Immermanns teorem:

NL=coNL

Litteratur

Michael Sipser: "Introduktion till teorin om beräkning"

Komplexitetsklasser av algoritmer
Anses som ljus	DLOGTIME AC 0 ACC 0 TC0 [ sv L SL RL NL NC SC CC P P-komplett ZPP RP BPP BQP EQP APX
Ska vara svårt	U.P. NP NP komplett co-NP co-NP-komplett AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplett
Anses vara svårt	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLA