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
BearbeitenEine Sprache liegt genau dann in der Komplexitätsklasse , wenn eine probabilistische Turingmaschine existiert, für die gilt:
- läuft für alle Eingaben in polynomieller Zeit
![{\displaystyle x\in {\mathcal {L}}\Rightarrow Pr[M(x)=1]\geq {\frac {1}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7abc1c8a1609feb9a8e10ae96e454c4d83cba628)
![{\displaystyle x\notin {\mathcal {L}}\Rightarrow Pr[M(x)=0]=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a690a958807d75d0bb1619b5e4953714dabe2a1d)
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.[1]
Im Gegensatz zur Komplexitätsklasse ZPP wird hier gefordert, dass die Laufzeit der Turingmaschine 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.[1]
Eigenschaften
BearbeitenRP ist abgeschlossen unter Vereinigung und Schnitt.[2] Das bedeutet, dass für zwei Sprachen auch . 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.[3]
Beziehung zu anderen Komplexitätsklassen
BearbeitenSowohl RP als auch co-RP liegen zwischen den Klassen ZPP (= RP co-RP) und BPP, es gilt also ZPP ⊆ RP ⊆ BPP und ZPP ⊆ co-RP ⊆ BPP.[2]
Außerdem gilt RP ⊆ NP und co-RP ⊆ co-NP.[2]
Wenn NP ⊆ BPP, dann gilt sogar NP = RP.[4]
Einzelnachweise
Bearbeiten- ↑ a b Sanjeev Arora und Boaz Barak: Computational Complexity: A Modern Approach. Cambridge University Press, 2009, ISBN 978-0-521-42426-4, S. 133.
- ↑ a b c Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 195.
- ↑ Daniel Pierre Bovet und Pierluigi Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994, ISBN 0-13-915380-2, S. 198,202.
- ↑ Johannes Köbler, Uwe Schöning, Jacobo Torán: The Graph Isomorphism Problem - It's Structural Complexity. Birkhäuser, 1993, ISBN 3-7643-3680-3, S. 73.
Literatur
Bearbeiten- Ingo Wegener: Komplexitätstheorie (S. 31–34) ISBN 3540001611
- Köbler, Schöning, Toran: The Graph Isomorphism Problem - It's Structural Complexity (S. 68 ff.) - ISBN 3-7643-3680-3
Weblinks
Bearbeiten- RP. In: Complexity Zoo. (englisch)