NL-Vollständigkeit

NL-Vollständigkeit

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=CoNL.

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:

LNLNCPNPPSPACE

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.

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. 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. Eine mögliche Probleminstanz wäre

(x_1 \vee \neg x_3) \wedge (\neg x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_2).

Die richtige Antwort für diese Formel lautet "ja", da beispielsweise x1 = 1,x2 = 0,x3 = 1 eine erfüllende Belegung der Variablen darstellt.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Vollständigkeit — (abgeleitet vom Ausdruck vollen Bestand haben) bezeichnet: allgemein die Eigenschaft einer Zusammenstellung oder Aufzählung, alle zu einer Gesamtheit gehörenden Bestandteile zu umfassen fachsprachlich eine mathematische Eigenschaft, siehe Glossar …   Deutsch Wikipedia

  • Vollständigkeit (Statistik) — Vollständigkeit ist in der mathematischen Statistik ein Begriff. Sie kann als Eigenschaft messbaren Funktionen zukommen, die aus dem Stichprobenraum in einen beliebigen Maßraum abbilden. Vollständigkeit wird für gewöhnlich zusammen mit Suffizienz …   Deutsch Wikipedia

  • Vollständigkeit — Vollständigkeit, die Eigenschaft eines aus mehren, mehr od. weniger auch als für sich bestehend denkbaren Theilen zusammengesetzten Gegenstandes, vermöge deren er die Gesammtheit der ihn constituirenden Theile, sowohl der Zahl, als auch der… …   Pierer's Universal-Lexikon

  • Vollständigkeit — ↑Exhaustivität, ↑Totalität …   Das große Fremdwörterbuch

  • Vollständigkeit (Logik) — Man bezeichnet ganz unterschiedliche Eigenschaften formaler Systeme bzw. Kalküle mit dem Begriff Vollständigkeit. Zur Unterscheidung werden die Begriffe Vollständigkeit von Theorien Vollständigkeit von Sequenzenkalkülen verwendet. Daneben wird… …   Deutsch Wikipedia

  • Vollständigkeit — Vollzähligkeit; Lückenlosigkeit * * * Vọll|stän|dig|keit 〈f. 20; unz.〉 vollständige Beschaffenheit, Ganzheit, Beisammensein aller dazugehörenden Teile ● der Vollständigkeit halber nur um die Sache zu vervollständigen (nicht weil es unbedingt… …   Universal-Lexikon

  • Vollständigkeit (Komplexitätstheorie) — In der theoretischen Informatik ist Vollständigkeit eine Eigenschaft von Problemen in Bezug auf eine Komplexitätsklasse. Intuitiv ist ein Problem dann vollständig für eine bestimmte Komplexitätsklasse, wenn kein anderes Problem der Klasse… …   Deutsch Wikipedia

  • Vollständigkeit (Analysis) — vollständiger Raum berührt die Spezialgebiete Mathematik Topologie Analysis Funktionalanalysis ist Spezialfall von topologischer Raum para …   Deutsch Wikipedia

  • Vollständigkeit, die — Die Vóllständigkeit, plur. inusit. die Eigenschaft, der Zustand, da ein Ding vollständig ist …   Grammatisch-kritisches Wörterbuch der Hochdeutschen Mundart

  • Vollständigkeit — (der Präferenzordnung), ⇡ Ordnungsaxiome …   Lexikon der Economics

  • Vollständigkeit — Vọll|stän|dig|keit, die; …   Die deutsche Rechtschreibung

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”