RL (Komplexität)

Randomisierter logarithmischer Raum (Rl),[1] manchmal genannt RLP (Randomisierte logarithmische Raumpolynomzeit),[2] ist der Komplexitätsklasse von Computerkomplexitätstheorie Probleme lösbar in logarithmischer Raum und Polynomzeit mit Probabilistische Turing -Maschinen mit einseitiger Fehler. Es wird in Analogie mit benannt RP, was ähnlich ist, aber keine logarithmische Raumbeschränkung hat.

Definition

Die probabilistischen Turing -Maschinen in der Definition von Rl Akzeptieren Sie niemals falsch, dürfen jedoch weniger als 1/3 der Zeit falsch ablehnen. das nennt man einseitiger Fehler. Die Konstante 1/3 ist willkürlich; irgendein x mit 0 <<< x < 1 would suffice. This error can be made 2p(x) Mal kleiner für jedes Polynom p(x) ohne mehr als Polynomzeit oder logarithmischer Speicherplatz durch wiederholtes Ausführen des Algorithmus.

Beziehung zu anderen Komplexitätsklassen

Manchmal der Name Rl ist für die Klasse von Problemen reserviert, die durch logarithmische Raum-probabilistische Maschinen in lösbar sind ungebunden Zeit. Es kann jedoch gezeigt werden, dass diese Klasse gleich ist Nl Verwendung eines probabilistischen Zählers und so wird normalerweise als als bezeichnet als Nl stattdessen; Dies zeigt auch das Rl ist in Nl. Rl ist in Bpl, was ähnlich ist, aber zweiseitigen Fehler (falsch akzeptiert). Rl enthält L, die Probleme lösbar durch deterministische Turing -Maschinen Im Protokollraum, da seine Definition nur allgemeiner ist.

Noam Nisan zeigten 1992 die Schwachen Derandomisierung resultieren Rl ist in SC,[3] die Klasse von Problemen, die in Polynomzeit und Polylogarithmic -Raum auf einer deterministischen Turing -Maschine lösbar sind; Mit anderen Worten, gegeben Polylogarithmic Raum, eine deterministische Maschine kann simulieren logarithmisch Raumprobabilistische Algorithmen.

Es wird angenommen, dass Rl ist gleich LDas heißt, dass die Polynom-Zeit-Logspace-Berechnung vollständig desandomisiert werden kann; Hauptbeweise dafür wurden von Reingold et al. im Jahr 2005.[4] Ein Beweis dafür ist der heilige Gral der Bemühungen auf dem Gebiet der bedingungslosen Derandomisierung von Komplexitätsklassen. Ein großer Schritt nach vorne war Omer Reingolds Beweis dafür Sl ist gleich L.

Verweise

  1. ^ Komplexitätszoo: Rl
  2. ^ A. Borodin, S. A. Cook, P.W. Dymond, W.L. Ruzzo und M. Tompa. Zwei Anwendungen der induktiven Zählung für Komplementationsprobleme. Siam Journal on Computing, 18 (3): 559–578. 1989.
  3. ^ Nisan, Noam (1992), "Rl ⊆ Sc", Verfahren des 24. ACM -Symposiums über die Computertheorie (STOC '92), Victoria, British Columbia, Kanada, S. 619–623, doi:10.1145/129712.129772.
  4. ^ O. Reingold und L. Trevisan und S. Vadhan. Pseudorandom wandert in doppelten Graphen und das Problem von RL vs. L, ECCC TR05-022, 2004.