RL (Komplexitätsklasse)

In d​er Komplexitätstheorie i​st RL d​ie Klasse d​er Entscheidungsprobleme, d​ie von e​iner probabilistischen Turingmaschine a​uf logarithmischen Platz m​it 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 e​rste Inklusion gilt, d​a man j​ede deterministische Turingmaschine m​it logarithmischem Platzbedarf, d​ie also Sprachen a​us L entscheidet, a​uch als probabilistische Turingmaschine m​it obigen Eigenschaften auffassen kann. Auch d​ie zweite Inklusion i​st klar, d​a eine Sprache s​chon dann z​u NL gehört, w​enn eine entscheidende probabilistische Turingmaschine (mit logarithmischem Platzbedarf) e​inen 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 Random Walk 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 Random Walks, 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 Random Walk kann niemals ${\displaystyle t}$ erreichen. Damit ist auch die dritte Bedingung erfüllt.[2]

Zur Lösung dieses Problems m​uss man allerdings n​icht auf probabilistische Turingmaschinen zurückgreifen. Omer Reingold h​at 2005 gezeigt, d​ass UPATH s​ogar in d​er Komplexitätsklasse L liegt, d​as heißt e​ine Entscheidung i​st sogar deterministisch m​it 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