NL (complessità)

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca

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 .

Visto che un problema accettato da una macchina deterministica lo è anche da una non deterministica, avremo che .

Problemi NL-completi

[modifica | modifica wikitesto]

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 e di un grafo orientato, è raggiungibile da . 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:

È 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:

.

Più precisamente, NL è contenuta in AC1. È 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:

Collegamenti esterni

[modifica | modifica wikitesto]