NL

NL ist die nichtdeterministische Variante von 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 Susdruck wahr macht.