USTCON

USTCON

Das Erreichbarkeitsproblem in Graphen (auch STCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten s zu einem Knoten t gibt. Existiert solch ein Weg, so ist t von s aus erreichbar. Andernfalls ist t von s aus nicht erreichbar.

Die Abkürzung STCON steht für engl. s-t-Connectivity, GAP für engl. Graph Accessibility Problem und REACH für engl. Reachability. Das analoge Problem für ungerichtete Graphen heißt USTCON.

Das Erreichbarkeitsproblem ist ein NL-vollständiges Problem. Es lässt sich beispielsweise mit Hilfe der Breitensuche oder der Tiefensuche lösen.

Aussagen und Sätze

Beweisidee für STCON ist NL-vollständig

Es ist zu zeigen, dass jedes Problem in NL auf STCON reduziert werden kann und STCON in NL liegt.

  1. Für STCON in NL muss man einen geeigneten Algorithmus angeben. Eine nichtdeterministische Turingmaschine (NTM) rät hierzu den (korrekten) Nachfolgerknoten, um den gesuchten Knoten zu finden. Der Platzverbrauch ist O(1), da lediglich der aktuelle Knoten gespeichert werden muss.
  2. Die Probleme in NL sind solche, die auf logarithmischen Platz von einer NTM gelöst werden können. Eine jede Turingmaschine besitzt einen Konfigurationsgraphen, welcher die verschieden Konfigurationen einer TM beschreibt (die Kopfposition, den Bandinhalt und den Zustand). Der Konfigurationsgraph einer NTM, welcher uns ein Problem in NL löst, ist, da die Mengeninklusion  NL \subseteq P gilt, von maximal polynomieller Größe. Um einen Weg, und damit eine Lösung für ein beliebiges Problem in NL zu finden, müssen wir nun lediglich das folgende Problem lösen: "Gibt es einen Weg vom Anfangszustand zum akzeptierenden Zustand?" Die Lösung für dieses Problem kann uns der oben angegebene Algorithmus liefern.

Quellen

  • Christos H. Papadimitriou: Computational Complexity. Addison Wesley, ISBN 978-0201530827

Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

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

  • SL (complexity) — In computational complexity theory, SL (Symmetric Logspace or Sym L) is the complexity class of problems log space reducible to USTCON ( undirected s t connectivity ), which is the problem of determining whether there exists a path between two… …   Wikipedia

  • Symmetric Turing machine — Definition of symmetric Turing machines: SL was first defined in 1982 by Lewis and Papadimitriou, [Jesper Jansson. [http://www.df.lth.se/ jj/Publications/STCON2.ps Deterministic Space Bounded Graph Connectivity Algorithms] . Manuscript. 1998.]… …   Wikipedia

  • LOGSPACE — In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können. Um logarithmischen Platzverbrauch definieren zu können, muss… …   Deutsch Wikipedia

  • Logarithmischer Platz — In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können. Um logarithmischen Platzverbrauch definieren zu können, muss… …   Deutsch Wikipedia

  • SL (Komplexitätsklasse) — In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können. Um logarithmischen Platzverbrauch definieren zu können, muss… …   Deutsch Wikipedia

  • L (complexity) — In computational complexity theory, L (also known as LSPACE) is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. Logarithmic space is sufficient to …   Wikipedia

  • Erreichbarkeitsproblem in Graphen — Das Erreichbarkeitsproblem in Graphen (auch STCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten s zu einem Knoten t gibt. Existiert solch ein Weg, so ist t von s aus erreichbar. Andernfalls ist t… …   Deutsch Wikipedia

  • L (Komplexitätsklasse) — In der Komplexitätstheorie bezeichnet L die Klasse der Entscheidungsprobleme, welche von einer deterministischen Turingmaschine mit logarithmischem Platzverbrauch gelöst werden können. Um logarithmischen Platzverbrauch definieren zu können, muss… …   Deutsch Wikipedia

  • STCON — Das Erreichbarkeitsproblem in Graphen (auch STCON, GAP, PATH oder REACH) behandelt die Frage, ob es in einem Graphen einen Weg von einem Knoten s zu einem Knoten t gibt. Existiert solch ein Weg, so ist t von s aus erreichbar. Andernfalls ist t… …   Deutsch Wikipedia

  • Liste von Komplexitätsklassen — Dies ist eine Liste von Komplexitätsklassen, die in der Komplexitätstheorie betrachtet werden. Die Klassen verwenden in ihren Definitionen verschiedene Maschinenmodelle. Die wichtigsten Modelle sind Turingmaschinen; diese können deterministisch,… …   Deutsch Wikipedia

Share the article and excerpts

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