RP Randomisierte Polynomzeit ist die Komplexitätsklasse der Computational complexity Theory, Probleme, für die eine probabilistische Turing-Maschine mit diesen Eigenschaften existiert:⁕Sie läuft immer in Polynomzeit in der Eingabegröße⁕Wenn die richtige Antwort NEIN ist, gibt sie immer NEIN zurück⁕Wenn die richtige Antwort JA ist, gibt sie JA mit einer Wahrscheinlichkeit von mindestens 1/2 zurück.Mit anderen Worten, der Algorithmus darf eine wirklich zufällige Münze werfen, während er läuft. Der einzige Fall, in dem der Algorithmus JA zurückgeben kann, ist, wenn die tatsächliche Antwort JA lautet; wenn der Algorithmus beendet wird und JA erzeugt, ist die richtige Antwort definitiv JA; Der Algorithmus kann jedoch unabhängig von der tatsächlichen Antwort ohne beenden. Das heißt, wenn der Algorithmus NEIN zurückgibt, ist er möglicherweise falsch.Einige Autoren nennen diese Klasse R, obwohl dieser Name häufiger für die Klasse der rekursiven Sprachen verwendet wird.Wenn die richtige Antwort JA lautet und der Algorithmus n−mal ausgeführt wird, wobei das Ergebnis jedes Laufs statistisch unabhängig von den anderen ist, gibt er mindestens einmal JA mit einer Wahrscheinlichkeit von mindestens 1 − 2- zurück. Wenn der Algorithmus also 100 Mal ausgeführt wird, ist die Wahrscheinlichkeit, dass er jedes Mal die falsche Antwort gibt, geringer als die Wahrscheinlichkeit, dass kosmische Strahlen den Speicher des Computers beschädigen, auf dem der Algorithmus ausgeführt wird. In diesem Sinne sind die meisten Algorithmen in RP sehr praktisch, wenn eine Quelle von Zufallszahlen verfügbar ist.

mehr sehen „