Co-RP (Komplexitätsklasse)
aus Wikipedia, der freien Enzyklopädie
 |
Der korrekte Titel dieses Artikels lautet „co-RP“. Diese Schreibweise ist aufgrund technischer Einschränkungen nicht möglich. |
co-RP (random polynominal) bzw. co-RP(ε(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 ε(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.
[Bearbeiten] Beziehung zu anderen Komplexitätsklassen
Die Klasse co-RP liegt zwischen den Klassen ZPP (= RP 
co-RP) und BPP, es gilt also ZPP ⊆ co-RP ⊆ BPP.
Außerdem gilt RP ⊆ NP und co-RP ⊆ co-NP.
[Bearbeiten] Literatur
- Wegener, Ingo. Komplexitätstheorie: S.31-34
