RL (Komplexitätsklasse)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der Komplexitätstheorie ist RL die Klasse der Entscheidungsprobleme, die von einer probabilistischen Turingmaschine auf logarithmischen Platz mit beschränkter einseitiger Irrtumswahrscheinlichkeit lösbar sind.

Definition[Bearbeiten]

Eine Sprache, das heißt eine Teilmenge L \subset \{0,1\}^*, gehört zur Klasse RL, falls es eine probabilistische Turingmaschine M gibt, so dass folgendes gilt:

  • Es gibt eine Konstante C>0, so dass jede mögliche Rechung von M auf einer Eingabe x\in\{0,1\}^n pro Arbeitsband höchstens C\cdot\log n Zellen verwendet.
  • Ist x\in L, so ist P(M(x)=1) \ge \textstyle\frac{2}{3} (beschränkte Irrtumswahrscheinlichkeit bei x\in L)
  • Ist x\notin L, so ist P(M(x)=1) = 0 (kein Irrtum bei x\notin L)

Dabei bedeutet M(x) das Ergebnis einer zufälligen Rechnung der Maschine M auf der Eingabe x. Die Wahrscheinlichkeit P bezieht sich auf alle möglichen Rechnungen.[1] Die willkürlich anmutende Wahrscheinlichkeit \textstyle \frac{2}{3} kann durch jede Zahl  0<p<1 ersetzt werden, ohne die Klasse RL zu verändern.

Beziehungen zu anderen Komplexitätsklassen[Bearbeiten]

Es gilt L \subset RL \subset NL.

Die erste Inklusion gilt, da man jede deterministische Turingmaschine mit logarithmischem Platzbedarf, die also Sprachen aus L entscheidet, auch als probabilistische Turingmaschine mit obigen Eigenschaften auffassen kann. Auch die zweite Inklusion ist klar, da eine Sprache schon dann zu NL gehört, wenn eine entscheidende probabilistische Turingmaschine (mit logarithmischem Platzbedarf) einen akzeptierenden Rechnungslauf hat.

Pfad in ungerichteten Graphen[Bearbeiten]

Bdekannt ist folgender Algorithmus einer solchen Turingmaschine, der entscheidet ob es in einem ungerichteten Graphen mit n Knoten zu zwei vorgebenen Knoten einen verbindenden Pfad gibt. Die Sprache ist also die Menge aller binären Kodierungen von Tripeln (G,s,t) von Graphen G und zwei ihrer Knoten s und t, für die es einen verbindenden Pfad gibt. Diese Sprache nennt man auch UPATH (für engl. undirected path)

Ein UPATH entscheidender Algorithmus im Sinne obiger Definition geht wie folgt vor: Man starte in s längs der Kanten des Graphen einen Random Walk und stoppe nach 100 n^4 Schritten oder wenn t erreicht wurde. Im letzten Fall gebe man 1 aus, sonst 0.

Der Platzbedarf dieses Algorithmus umfasst einen Zähler für die Schrittzahl und einen Speicher für den aktuellen Knoten des Random Walks, beides ist durch ein konstanten Vielfaches von \log n machbar. Damit erfüllt der Algorithmus, das heißt die zugehörige probabilistische Turingmaschine, die erste der drei Bedingungen. Man kann zeigen, dass wegen der hinreichend hohen Schrittzahl 100 n^4 auch die zweite Bedingung erfüllt ist, das heißt der Algorithmus mit hinreichend großer Wahrscheinlichkeit t findet, falls die Kodierung von (G,s,t) in UPATH liegt. Anderenfalls, das heißt wenn t von s aus nicht erreichbar ist, so kann der Algorithmus nur 0 ausgeben, denn der Random Walk kann niemals t erreichen; damit ist auch die dritte Bedingung erfüllt.[2]

Zur Lösung dieses Problems muss man allerdings nicht auf probabilistische Turingmaschinen zurückgreifen. Omer Reingold hat 2005 gezeigt, dass UPATH sogar in der Komplexitätsklasse L liegt, das heißt eine Entscheidung ist sogar deterministisch mit logarithmischem Platzbedarf möglich.[3]

Einzelnachweise[Bearbeiten]

  1. Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press (2009), ISBN 978-0-521-42426-4, Abschnitt 7.7: Randomized Space-Bounded Computation
  2. R. Aleliunas, R.M. Karp, L. Lipton, L. Lovász, C. Rackoff: Random walks, universal traversal sequences, and the complexity of maze problems (1979), FOCS Seiten 218-233 (54th Annual Symposium on Foundations of Computer Science)
  3. Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press (2009), ISBN 978-0-521-42426-4, Theorem 21.21: Reingold's Theorem