NL (complessità)

La classe NL (abbreviazione di nondeterministic logarithmic space, ovvero "spazio logaritmico non deterministico", nota anche come NLOGSPACE) è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con $S_{M}(n)=O(\log n)$.

Visto che un problema accettato da una macchina deterministica lo è anche da una non deterministica, avremo che ${\mathsf {L}}\subseteq {\mathsf {NL}}$.

Problemi NL-completi

Diversi problemi decisionali sono noti essere NL-completi sotto riduzioni log-space, fra cui la st-connectivity e la 2-satisfiability. Il problema di st-connectivity consiste nel decidere se, presi due nodi $s$ e $t$ di un grafo orientato, $t$ è raggiungibile da $s$. La 2-satisfiability consiste invece nel decidere se, prese una formula proposizionale in cui ogni clausola è la disgiunzione di due letterali, esiste un'assegnazione di valori di verità per tali letterali che rende la formula vera. Ad esempio, verificare se la seguente formula è o meno soddisfacibile:

$(x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})$

Contenimenti

È ben noto che NL è contenuta in P, dato che esiste un algoritmo in tempo polinomiale per la 2-satisfiability, ma non è noto se NL = P o se L = NL. È tuttavia noto che NL = co-NL, dove co-NL è la classe dei problemi il cui complemento è in NL. Questo risultato è noto come teorema di Immerman–Szelepcsényi, in quanto fu scoperto indipendentemente da Neil Immerman e Róbert Szelepcsényi nel 1987; nel 1995 entrambi ricevettero il premio Gödel per questa scoperta.

Nella complessità dei circuiti, NL può essere posizionata all'interno della gerarchia NC. Dal lavoro di Papadimitriou del 1994 (teorema 16.1), abbiamo che:

${\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}$.

Più precisamente, NL è contenuta in AC¹. È noto che NL è uguale a ZPL, la classe dei problemi risolvibili da algoritmi randomizzati in spazio logaritmico in tempo indefinito, senza errori. No è nota, tuttavia, né congetturata essere uguale a RLP o ZPLP, le restrizioni in tempo polinomiale di RL and ZPL.

Dal teorema di Savitch abbiamo inoltre che:

${\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalentemente, }}{\mathsf {NL\subseteq L}}^{2}.$

Bibliografia

• (EN) C. Papadimitriou, Chapter 16: Logarithmic Space, in Computational Complexity, Addison-Wesley, 1994, ISBN 0-201-53082-1.
• (EN) Michael Sipser, Sections 8.4–8.6: The Classes L and NL, NL-completeness, NL equals coNL, in Introduction to the Theory of Computation, PWS Publishing, 27 giugno 1997, pp. 294–302, ISBN 0-534-94728-X.

Collegamenti esterni

• (EN) NL: Nondeterministic Logarithmic-Space, su complexityzoo.net.
• (EN) Oded Goldreich, Introduction to Complexity Theory: Lecture 7 (ps), su wisdom.weizmann.ac.il. URL consultato il 20 dicembre 2022 (archiviato dall'url originale il 3 marzo 2016). Proposition 6.1.