25. Jun 2008, 02:23

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

Dieser Artikel ist eine Kopie aus der freien Enzyklopädie Wikipedia. Am Originalartikel kann jeder Korrekturen und Ergänzungen vornehmen. Zudem kann man frühere Versionen einsehen.

Abkürzungen • Dateiendungen • Netzjargon