RP (Komplexitätsklasse)
# RP (Komplexitätsklasse)

RP (englisch randomized polynomial time, manchmal auch nur mit R bezeichnet) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe eine Fehlerwahrscheinlichkeit von höchstens 1/2 hat. Die Verwendung einer beliebigen anderen konstanten Fehlerschranke kleiner als 1 ändert nichts an der Definition der Klasse RP, durch mehrmalige Anwendung eines gegebenen RP-Algorithmus lässt sich jede beliebige Fehlerschranke erreichen.

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

Sie wurde 1977 mit anderen probabilistichen Komplexitätsklassen von John T. Gill eingeführt.

## Definition

Eine Sprache ${\mathcal {L}}$ liegt genau dann in der Komplexitätsklasse ${\mathcal {RP}}$, wenn eine probabilistische Turingmaschine $M$ existiert, für die gilt:

* $M$ läuft für alle Eingaben in polynomieller Zeit
* $x\in {\mathcal {L}}\Rightarrow Pr[M(x)=1]\geq {\frac {1}{2}}$
* $x\notin {\mathcal {L}}\Rightarrow Pr[M(x)=0]=1$

Die Konstante 1/2 ist willkürlich gewählt. Jede beliebige Konstante echt größer als 0 und weniger als 1 führt zu einer äquivalenten Definition.

Im Gegensatz zur Komplexitätsklasse ZPP wird hier gefordert, dass die Laufzeit der Turingmaschine $M$ für alle Eingaben polynomiell ist. Diese Forderung kann abgeschwächt werden, so dass wie bei ZPP nur noch gefordert wird, dass der Erwartungswert der Laufzeit durch ein Polynom beschränkt ist; die beiden Definitionen sind äquivalent.

## Eigenschaften

RP ist abgeschlossen unter Vereinigung und Schnitt. Das bedeutet, dass für zwei Sprachen $L_{1},L_{2}\in {\mathcal {RP}}$ auch $L_{1}\cup L_{2},L_{1}\cap L_{2}\in {\mathcal {RP}}$. Es ist unbekannt, ob RP unter Komplementbildung abgeschlossen ist, die Komplementklasse von RP ist die Komplexitätsklasse co-RP.

Es ist kein RP-vollständiges Problem bekannt und es gibt Hinweise darauf, dass es keine RP-vollständigen Probleme gibt.

## Beziehung zu anderen Komplexitätsklassen

Sowohl RP als auch co-RP liegen zwischen den Klassen ZPP (= RP $\cap$ co-RP) und BPP, es gilt also ZPP ⊆ RP ⊆ BPP und ZPP ⊆ co-RP ⊆ BPP.

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

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

