NL

NL ist die nichtdeterministische Variante von L, $\operatorname{NSPACE}(\log)$.

Bemerkung: $N\subseteq NL$

Beispiel

Das 2SAT-Problem ist in NL:

Gegeben ist eine logische Formel die sich aus boole'schen Variablen $x_i$ zusammensetzt, die potentiell von einem Negationszeichen $\neg x_i$ negiert wird. Immer zwei dieser Variablen oder negierten Variablen werden mit einem oder-Zeichen $\vee$ verbunden. Diese Disjunktionen werden dann wiederum durch und-Zeichen $\wedge$ verknüpft. Beispiel:

$ (x_1\vee\neg x_2) \wedge (\neg x_2 \vee x_3) \wedge (x_3 \vee x_4) $

Die Frage ist nun, ob man, gegeben einen 2SAT-Ausdruck, eine Belegung finden kann, die diesen Ausdruck wahr macht.

Da wir nichtdeterministisch arbeiten, reicht es, dass wir davon ausgehen, dass auf unserem Orakelband eine solche lösende Belegung gespeichert ist. Zu Überprüfen ob der Ausdruck dann wahr ist ist trivial.