NL (Komplexitätsklasse)
In der Komplexitätstheorie bezeichnet NL 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.
| Inhaltsverzeichnis |
Eigenschaften
Nach dem Satz von Immerman/Szelepcsenyi ist die Klasse NL unter Komplement abgeschlossen, es gilt also 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:
Nach dem Platzhierarchiesatz muss mindestens eine dieser Inklusionen echt sein, da L eine echte Teilmenge von PSPACE ist. Bisher ist aber unbekannt, welche dies ist, und ob beispielsweise L=NL gilt.
Bekannt ist allerdings, dass die Gleichheit NL=RL gilt, RL ist dabei analog zu NL für probabilistischen Turingmaschinen definiert.
NL-vollständige Probleme
Das Problem, ob in einem gerichteten Graphen ein Weg zwischen zwei gegebenen Knoten existiert (STCON), ist NL-vollständig. Das bedeutet, dass das Problem nicht nur selber in NL liegt, sondern dass sich weiterhin jedes andere Problem in NL auf STCON reduzieren lässt. Die Berechnung der Reduktionsfunktion verwendet dabei selber auch nur logarithmisch viel Platz.
Ein weiteres wichtiges NL-vollständiges Problem ist 2-SAT, eine eingeschränkte Variante des NP-vollständigen Erfüllbarkeitsproblems der Aussagenlogik. Bei 2-SAT soll entschieden werden, ob eine gegebene aussagenlogische Formel in konjunktiver Normalform mit jeweils zwei Literalen pro Klausel erfüllt werden kann. Eine mögliche Probleminstanz wäre
.
Die richtige Antwort für diese Formel lautet "ja", da beispielsweise x1 = W,x2 = F,x3 = W eine erfüllende Belegung der Variablen darstellt.
Weblinks
- NL im Complexity Zoo (englisch)