RP (Komplexitätsklasse)
aus Wikipedia, der freien Enzyklopädie
RP (random polynominal) bzw. RP(ε(n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe der Länge n eine durch ε(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 der Sprache L zum Komplement co-L über, so erhält man die Komplexitätsklasse co-RP.
[Bearbeiten] Beziehung zu anderen Komplexitätsklassen
Die Klasse RP liegt zwischen den Klassen ZPP (= RP 
co-RP) und BPP, es gilt also ZPP ⊆ RP ⊆ BPP.
Außerdem gilt 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.
[Bearbeiten] Literatur
- Ingo Wegener: Komplexitätstheorie (S.31-34) ISBN 3540001611
