L és NL osztály

Ez a cikk egy determinisztikus Turing-gép nyelvi osztályairól szól. A unix segédprogramról szóló cikk az nl .

Az L nyelvosztály azon nyelvek halmaza, amelyek eldönthetők egy determinisztikus Turing-gépen , amely további memóriát használ az n hosszúságú bemenethez. $O(\log(n))$

Az NL nyelvek osztálya azoknak a nyelveknek a halmaza, amelyek eldönthetők egy nem determinisztikus Turing-gépen , amely további memóriát használ az n hosszúságú bemenethez. $O(\log(n))$

Példák:

$\{0^{k}1^{k}:k\geq 0\}\in L$
Legyen a nyelv egy irányított gráf , amelyben van egy út s-től t -ig $PATH=\{(G,s,t):G$ $\}$ $PATH\NL nyelven$

NL-teljes problémák

A naplómemória konverter egy Turing-gép három szalaggal: egy csak olvasható bemeneti szalaggal, egy csak írható kimeneti szalaggal és egy munkaszalaggal, amely legfeljebb O(log(n)) cellát használhat.

Az ilyen konverter által kiszámított függvényt logaritmikus memóriával számított függvénynek nevezzük .

Az A feladat logaritmikusan redukálja a memóriát a B feladatra, ha van olyan logaritmikus függvény a memóriából, amely az A feladatot B feladatra redukálja . $A\leq _{L}B$

Egy nyelvet NL-teljesnek nevezünk, ha az NL-hez tartozik, és az NL-ben lévő bármely nyelv logaritmikusan redukálható rá a memóriából.

Tétel:

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

Következmény:

Ha egy NL-teljes nyelv L-hez tartozik, akkor L = NL

Nyilatkozat:

A PATH egy NL-teljes feladat.

Következmény:

NL\subseteq P

Immermann-tétel

osztály coNL - olyan nyelvek, amelyek kiegészítései NL-ben vannak.

Immermann tétele:

NL = conNL

Irodalom

Michael Sipser: „Bevezetés a számításelméletbe”

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES