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 $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 Rechnung 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)\geq \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. 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

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

Bekannt ist folgender Algorithmus einer solchen Turingmaschine, der entscheidet ob es in einem ungerichteten Graphen mit $n$ Knoten zu zwei vorgegebenen 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 $100n^{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 konstantes 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 $100n^{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.

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.