In der Kompliziertheitstheorie ist RP ("randomized polynomische Zeit") die Kompliziertheitsklasse von Problemen, für die eine probabilistic Maschine von Turing mit diesen Eigenschaften besteht:

• Es läuft immer in der polynomischen Zeit mit der Eingangsgröße
• Wenn die richtige Antwort ist, Nein, gibt sie immer KEINEN zurück
• Wenn die richtige Antwort ist JA, dann gibt sie JA mit der Wahrscheinlichkeit mindestens 1/2 zurück (sonst, sie kehrt NICHT zurück).

Mit anderen Worten wird dem Algorithmus erlaubt, eine aufrichtig zufällige Münze zu schnipsen, während er läuft. Der einzige Fall, in dem der Algorithmus JA zurückgeben kann, ist, wenn die wirkliche Antwort JA ist; deshalb, wenn der Algorithmus begrenzt und erzeugt JA, dann ist die richtige Antwort bestimmt JA; jedoch kann der Algorithmus ohne unabhängig von der wirklichen Antwort enden. D. h. wenn der Algorithmus zurückkehrt, Nein, könnte er falsch sein.

Einige Autoren nennen diese Klasse R, obwohl dieser Name für die Klasse von rekursiven Sprachen allgemeiner verwendet wird.

Wenn die richtige Antwort JA ist und der Algorithmus n Zeiten mit dem Ergebnis jedes von anderen statistisch unabhängigen Laufs geführt wird, dann wird es JA mindestens einmal mit der Wahrscheinlichkeit mindestens zurückgeben. So, wenn der Algorithmus 100mal geführt wird, dann die Chance davon, die falsche Antwort gebend jedes Mal ist niedriger als die Chance, dass kosmische Strahlen das Gedächtnis des Computers verdorben haben, der den Algorithmus führt. In diesem Sinn, wenn eine Quelle von Zufallszahlen verfügbar ist, sind die meisten Algorithmen in RP hoch praktisch.

Der Bruchteil 1/2 in der Definition ist willkürlich. Der Satz-RP wird genau dieselben Probleme enthalten, selbst wenn der 1/2 durch unveränderliche Nichtnullwahrscheinlichkeit weniger als 1 ersetzt wird; hier unveränderliche Mittel, die des Eingangs zum Algorithmus unabhängig sind.

Zusammenhängende Kompliziertheitsklassen

Die Definition von RP sagt, dass JA Antwort ist immer richtig, und dass KEINE Antwort gewöhnlich richtig ist. Die Kompliziertheitsklassenhandelsgesellschaft wird ähnlich definiert, außer dass immer NICHT richtig ist und JA gewöhnlich richtig ist. Mit anderen Worten akzeptiert es alle JA Beispiele, aber kann entweder akzeptieren oder KEINE Beispiele zurückweisen. Der Klassen-BPP beschreibt Algorithmen, die falsche Antworten sowohl auf JA als auch auf KEINEN Beispielen geben können, und so sowohl RP als auch Handelsgesellschaft enthalten. Die Kreuzung der Sätze RP und Handelsgesellschaft wird ZPP genannt. Wie RP R genannt werden kann, verwenden einige Autoren den Namen mein Gott aber nicht die Handelsgesellschaft.

Verbindung zu P und NP

P ist eine Teilmenge von RP, der eine Teilmenge von NP ist. Ähnlich ist P eine Teilmenge der Handelsgesellschaft, die eine Teilmenge von co-NP ist. Es ist nicht bekannt, ob diese Einschließungen streng sind. Jedoch, wenn die allgemein geglaubte Vermutung P = BPP wahr ist, dann RP, Handelsgesellschaft und P-Zusammenbruch (sind alle gleich). Außerdem annehmend, dass P  NP, das dann andeutet, dass RP in NP ausschließlich enthalten wird. Es ist nicht bekannt, ob RP = Handelsgesellschaft, oder ob RP eine Teilmenge der Kreuzung von NP und co-NP ist, obwohl das durch P = BPP einbezogen würde.

Ein natürliches Beispiel eines Problems in der Handelsgesellschaft, die zurzeit nicht bekannt ist, in P zu sein, ist Polynomische Identitätsprüfung, das Problem des Entscheidens, ob ein gegebener multivariate arithmetischer Ausdruck über die ganzen Zahlen das Nullpolynom ist. Zum Beispiel, ist das Nullpolynom während

ist nicht.

Eine alternative Charakterisierung von RP, der manchmal leichter ist zu verwenden, ist der Satz von durch nichtdeterministische Maschinen von Turing erkennbaren Problemen, wo die Maschine akzeptiert, ob, und nur wenn mindestens ein unveränderlicher Bruchteil der Berechnungspfade, die der Eingangsgröße unabhängig sind, akzeptiert. NP andererseits, braucht nur einen akzeptierenden Pfad, der einen exponential kleinen Bruchteil der Pfade einsetzen konnte. Diese Charakterisierung macht die Tatsache, dass RP eine Teilmenge von offensichtlichem NP ist.

Siehe auch

• Randomized-Algorithmus

Außenverbindungen

• RP am Kompliziertheitszoo