Luokat L ja NL

Tämä artikkeli käsittelee deterministisen Turingin koneen kieliluokkia. Unix-apuohjelmaa käsittelevän artikkelin nimi on nl .

Kieliluokka L on joukko kieliä, jotka ovat päätettävissä deterministisellä Turingin koneella, joka käyttää lisämuistia pituuden n syötteelle. $O(\log(n))$

NL-kielten luokka on joukko kieliä, jotka ovat päätettävissä ei - deterministisellä Turingin koneella, joka käyttää lisämuistia pituuden n syötteelle. $O(\log(n))$

Esimerkkejä:

$\{0^{k}1^{k}:k\geq 0\}\in L$
Olkoon kieli sitten suunnattu graafi , jossa on polku s:stä t :hen $PATH=\{(G,s,t):G$ $\}$ $PATH\NL$

NL-täydelliset ongelmat

Lokimuistimuunnin on Turingin kone, jossa on kolme nauhaa: vain luku -syöttönauha, vain kirjoitus -lähtönauha ja työnauha, joka voi käyttää enintään O(log(n))-solua.

Tällaisen muuntimen laskemaa funktiota kutsutaan logaritmisella muistilla lasketuksi funktioksi .

Tehtävä A pienentää logaritmisella muistista tehtävään B, jos muistista on logaritminen funktio, joka pienentää tehtävän A tehtäväksi B. Merkitään $A\leq _{L}B$

Kieltä kutsutaan NL-täydelliseksi , jos se kuuluu NL:ään ja mikä tahansa NL:n kieli voidaan pelkistää siihen logaritmisesti muistista.

Lause:

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

Seuraus:

Jos NL-täydellinen kieli kuuluu L:lle, niin L = NL

Lausunto:

PATH on NL-täydellinen tehtävä.

Seuraus:

NL\subseteq P

Immermannin lause

luokka coNL - kielet, joiden täydennykset ovat Alankomaissa.

Immermannin lause:

NL = conNL

Kirjallisuus

Michael Sipser: "Johdatus laskentateoriaan"

Algoritmien monimutkaisuusluokat
Kevyenä pidetty	DLOGTIME AC 0 ACC 0 TC0 [ fi L SL RL NL NC SC CC P P-täydellinen ZPP RP BPP BQP EQP APX
Taitaa olla vaikeaa	U.P. NP NP valmis co-NP co-NP-täydellinen AM M.A. QMA PH ⊕P PP #P #P - IP_ PSPACE PSPACE-täydellinen
Vaikeaksi pidetty	EXPTIME NEXPTIME EXPACE 2-EXPTIME ELEMENTARY R PR RE täytä uudelleen Co-RE Co-RE-complete KAIKKI