NL (Komplexitätsklasse)

In der Komplexitätstheorie bezeichnet NL (für nichtdeterministisch logarithmischer Platz) die Klasse der Entscheidungsprobleme, die von einer nichtdeterministischen Turingmaschine auf logarithmischem Platz gelöst werden können.

NL ist eine Erweiterung der Klasse L, die analog für deterministische Turingmaschinen definiert ist.

Eigenschaften

Nach dem Satz von Immerman und Szelepcsényi ist die Klasse NL unter Komplement abgeschlossen. Wenn co-NL die Klasse von Sprachen ist, welche das Komplement von NL bildet, dann gilt NL = co-NL.

Beziehung zu anderen Komplexitätsklassen

Da NL die Generalisierung der Klasse L ist, ist jedes Problem in L auch in NL. Darüber hinaus sind die folgenden Beziehungen bekannt:

L ⊆ NL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE

In obiger Kette ist für keine Inklusion bekannt, ob sie echt ist. Die einzigen transitiven Inklusionen, für die die Echtheit bekannt ist, sind:

• L ⊂ PSPACE
• NL ⊂ PSPACE

Dies ergibt sich aus dem Platzhierarchiesatz. Für die zweite Zeile wird noch der Satz von Savitch benötigt.

Bekannt ist allerdings, dass die Gleichheit NL = RL gilt. Die Klasse RL ist analog zu NL für probabilistische Turingmaschinen definiert.

Mit dem Polynomialzeitalgorithmus für 2-SAT folgt, dass NL in P enthalten ist, aber es ist nicht bekannt, ob NL = P oder ob L = NL ist.

NL-vollständige Probleme

Die Klasse NL enthält vollständige Probleme. Dies bedeutet, dass ein Problem nicht nur selbst in NL liegt, sondern dass sich weiterhin jedes andere Problem der Klasse NL auf dieses Problem reduzieren lässt. Die Berechnung der Reduktionsfunktion benötigt dabei ebenfalls nur logarithmisch viel Platz.

Erreichbarkeitsproblem in Graphen

Das Entscheidungsproblem, ob in einem gerichteten Graphen ein Weg zwischen zwei gegebenen Knoten existiert (STCON), ist NL-vollständig.

2-SAT

Ein weiteres wichtiges NL-vollständiges Problem ist 2-SAT, eine eingeschränkte Variante des NP-vollständigen Erfüllbarkeitsproblems der Aussagenlogik. 2-SAT ist allerdings in Polynomialzeit lösbar. Bei 2-SAT soll entschieden werden, ob eine gegebene aussagenlogische Formel erfüllt werden kann, die in konjunktiver Normalform mit jeweils zwei Literalen pro Klausel vorliegt. Sei $\varphi$ eine aussagenlogische Formel. Eine mögliche Probleminstanz wäre dann

$\varphi :=(x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})$.

Die obige Formel ist eine "Ja-Instanz" für das Problem, da beispielsweise die Belegung $\beta$ mit $\beta (x_{1})=1,\beta (x_{2})=0,\beta (x_{3})=1$ existiert, welche eine erfüllende Belegung der Variablen darstellt.

Weblinks

• NL. In: Complexity Zoo. (englisch)