RL (Komplexitätsklasse)

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

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

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

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

Beziehungen zu anderen Komplexitätsklassen

Es gilt L ${\displaystyle \subset }$ RL ${\displaystyle \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

Bekannt ist folgender Algorithmus einer solchen Turingmaschine, der entscheidet, ob es in einem ungerichteten Graphen mit ${\displaystyle n}$ Knoten zu zwei vorgegebenen Knoten einen verbindenden Pfad gibt. Die Sprache ist also die Menge aller binären Kodierungen von Tripeln ${\displaystyle (G,s,t)}$ von Graphen ${\displaystyle G}$ und zwei ihrer Knoten ${\displaystyle s}$ und ${\displaystyle 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 ${\displaystyle s}$ längs der Kanten des Graphen einen Zufallspfad und stoppe nach ${\displaystyle 100n^{4}}$ Schritten oder wenn ${\displaystyle 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 Zufallspfades, beides ist durch ein konstantes Vielfaches von ${\displaystyle \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 ${\displaystyle 100n^{4}}$ auch die zweite Bedingung erfüllt ist, das heißt der Algorithmus mit hinreichend großer Wahrscheinlichkeit ${\displaystyle t}$ findet, falls die Kodierung von ${\displaystyle (G,s,t)}$ in UPATH liegt. Anderenfalls, das heißt wenn ${\displaystyle t}$ von ${\displaystyle s}$ aus nicht erreichbar ist, so kann der Algorithmus nur 0 ausgeben, denn der Zufallspfad kann niemals ${\displaystyle 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

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