Co-RP

co-RP (random polynominal) bzw. co-RP($\epsilon$(n)) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomineller maximaler Rechenzeit gibt, der jede zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 annimmt und für jede nicht 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 der Sprache co-L zum Komplement L über, so erhält man die Komplexitätsklasse RP.

Beziehung zu anderen Komplexitätsklassen

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

Außerdem gilt RP ⊆ NP und co-RP ⊆ co-NP.

Literatur

• Wegener, Ingo. Komplexitätstheorie: S.31-34