RP (Komplexitätsklasse)

RP (random polynomial) bzw. RP($\epsilon$(n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus A mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe der Länge n eine durch $\epsilon$(n) beschränkte Fehlerwahrscheinlichkeit hat.

Dieser Fehlertyp wird als einseitiger Fehler (one-sided error) bezeichnet, im Gegensatz zu dem zweiseitigen Fehler (two-sided error) bei der Komplexitätsklasse BPP.

Geht man von einer Sprache L $\in$ RP zum Komplement co-L über, so erhält man die Komplexitätsklasse co-RP.

Beziehung zu anderen Komplexitätsklassen

Die Klasse RP liegt zwischen den Klassen ZPP (= RP $\cap$ co-RP) und BPP, es gilt also ZPP ⊆ RP ⊆ BPP

Außerdem gilt P ⊆ RP $\cap$ co-RP ⊆ RP ⊆ NP und co-RP ⊆ co-NP. Für den Fall RP(1) = RP* gilt sogar RP* = NP, ein RP-Algorithmus ohne Beschränkung der Fehlerwahrscheinlichkeit ist also in jedem Fall auch auf einer nichtdeterministischen Turingmaschine entscheidbar.

Wenn NP ⊆ BPP, dann gilt sogar NP = RP.

Literatur

• Ingo Wegener: Komplexitätstheorie (S.31-34) ISBN 3540001611
• Köbler, Schöning, Toran: The Graph Isomorphism Problem - It's Structural Complexity (S. 68 ff.) - ISBN 3-7643-3680-3