Klasse L og NL

Denne artikel handler om sprogklasser for en deterministisk Turing-maskine. Artiklen om unix-værktøjet hedder nl .

Sprogklassen L er det sæt af sprog, der kan bestemmes på en deterministisk Turing-maskine, der bruger ekstra hukommelse til et input med længden n. $O(\log(n))$

Klassen af NL-sprog er det sæt af sprog, der kan bestemmes på en ikke -deterministisk Turing-maskine, der bruger ekstra hukommelse til et input med længden n. $O(\log(n))$

Eksempler:

$\{0^{k}1^{k}:k\geq 0\}\i L$
Lad sproget være en rettet graf , hvor der er en vej fra s til t , så $PATH=\{(G,s,t):G$ $\}$ $PATH\i NL$

NL-komplette problemer

En log-hukommelseskonverter er en Turing-maskine med tre bånd: et skrivebeskyttet inputbånd, et skrivebeskyttet outputbånd og et arbejdsbånd, der ikke kan bruge mere end O(log(n)) celler.

Funktionen beregnet af en sådan konverter kaldes en funktion beregnet med logaritmisk hukommelse .

Opgave A reducerer logaritmisk fra hukommelse til opgave B , hvis der er en funktion logaritmisk fra hukommelse, der reducerer opgave A til opgave B. Benævnt $A\leq _{L}B$

Et sprog kaldes NL-komplet , hvis det tilhører NL, og ethvert sprog i NL kan reduceres til det logaritmisk fra hukommelsen.

Sætning:

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

Følge:

Hvis et NL-komplet sprog hører til L, så L = NL

Udmelding:

PATH er en NL-fuldendt opgave.

Følge:

NL\subseteq P

Immermanns sætning

klasse coNL - sprog, hvis komplementer er i NL.

Immermanns sætning:

NL=coNL

Litteratur

Michael Sipser: "Introduktion til teorien om beregning"

Kompleksitetsklasser af algoritmer
Betragtes som lys	DLOGTIME AC 0 ACC 0 TC0 [ da L SL RL NL NC SC CC P P-komplet ZPP RP BPP BQP EQP APX
Formodes at være svært	U.P. NP NP komplet co-NP co-NP-komplet AM M.A. QMA PH ⊕P PP #P #P- IP PSPACE PSPACE-komplet
Anses for vanskelig	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY R PR RE RE-complete Co-RE Co-RE-complete ALLE