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  , gehört zur Klasse RL, falls es eine probabilistische Turingmaschine   gibt, so dass folgendes gilt:

  • Es gibt eine Konstante  , so dass jede mögliche Rechnung von   auf einer Eingabe   pro Arbeitsband höchstens   Zellen verwendet.
  • Ist  , so ist   (beschränkte Irrtumswahrscheinlichkeit bei  )
  • Ist  , so ist   (kein Irrtum bei  )

Dabei bedeutet   das Ergebnis einer zufälligen Rechnung der Maschine   auf der Eingabe  . Die Wahrscheinlichkeit   bezieht sich auf alle möglichen Rechnungen.[1] Die willkürlich anmutende Wahrscheinlichkeit   kann durch jede Zahl   ersetzt werden, ohne die Klasse RL zu verändern.

Beziehungen zu anderen Komplexitätsklassen

Bearbeiten

Es gilt L   RL   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

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