RP (Komplexität)

Im Computerkomplexitätstheorie, Randomisierte Polynomzeit (RP) ist der Komplexitätsklasse von Problemen, für die a Probabilistische Turing -Maschine existiert mit diesen Eigenschaften:

RP -Algorithmus (1 Lauf)
Antwort produziert
Richtig
Antworten
Ja Nein
Ja ≥ 1/2 ≤ 1/2
Nein 0 1
RP -Algorithmus (n läuft)
Antwort produziert
Richtig
Antworten
Ja Nein
Ja ≥ 1 - 2n ≤ 2n
Nein 0 1
Co-RP-Algorithmus (1 Lauf)
Antwort produziert
Richtig
Antworten
Ja Nein
Ja 1 0
Nein ≤ 1/2 ≥ 1/2
  • Es läuft immer in der Polynomzeit in der Eingangsgröße
  • Wenn die richtige Antwort nein ist, gibt sie immer nein zurück
  • Wenn die korrekte Antwort Ja ist, gibt sie Ja mit Wahrscheinlichkeit mindestens 1/2 zurück (ansonsten kehrt sie nein zurück).

Mit anderen Worten, die Algorithmus darf während des Laufens eine wirklich zufällige Münze umdrehen. Der einzige Fall, in dem der Algorithmus Ja zurückgeben kann, ist, wenn die tatsächliche Antwort Ja ist. Wenn der Algorithmus endet und ja, ist die richtige Antwort definitiv ja; Der Algorithmus kann jedoch mit NO enden trotzdem der tatsächlichen Antwort. Das heißt, wenn der Algorithmus nein zurückgibt, könnte es falsch sein.

Einige Autoren nennen diese Klasse R, obwohl dieser Name häufiger für die Klasse von verwendet wird rekursive Sprachen.

Wenn die richtige Antwort Ja ist und der Algorithmus ausgeführt wird n Zeiten mit dem Ergebnis jedes Laufs statistisch unabhängig von den anderen wird es dann mindestens einmal mit Wahrscheinlichkeit mit mindestens einmal mit Ja zurückkehren 1 - 2n. Wenn der Algorithmus also 100 Mal ausgeführt wird, ist die Wahrscheinlichkeit, dass er jedes Mal die falsche Antwort gibt, niedriger als die Wahrscheinlichkeit, dass kosmische Strahlen den Speicher des Computers verfälscht haben, der den Algorithmus ausführte.[1] In diesem Sinne, wenn eine Quelle von Zufallszahlen verfügbar ist, sind die meisten Algorithmen in RP sind sehr praktisch.

Der Bruch 1/2 in der Definition ist willkürlich. Der Satz RP enthält genau die gleichen Probleme, auch wenn die 1/2 durch eine konstante Wahrscheinlichkeit von ungleich Null von weniger als 1 ersetzt wird; Hier bedeutet konstante Mittel unabhängig von der Eingabe zum Algorithmus.

Formale Definition

Eine Sprache L ist in RP Wenn und nur wenn es vorhanden ist a Probabilistische Turing -Maschine M, so dass

  • M Läuft für Polynomzeit für alle Eingänge
  • Für alle x in L, M Ausgänge 1 mit Wahrscheinlichkeit größer oder gleich 1/2
  • Für alle x nicht in L, M Ausgänge 0

Alternative, RP kann mit nur deterministischen Turing -Maschinen definiert werden. Eine Sprache L ist in RP Wenn und nur wenn es ein Polynom gibt p und deterministische Turing -Maschine M, so dass

  • M Läuft für Polynomzeit für alle Eingänge
  • Für alle x in L, der Bruchteil der Saiten y von Länge p(|x|) was befriedigt ist größer als oder gleich 1/2
  • Für alle x nicht in Lund alle Saiten y von Länge p(|x|),,

In dieser Definition die Zeichenfolge y Entspricht der Ausgabe der zufälligen Münzflips, die die probabilistische Turing -Maschine gemacht hätte. Für einige Anwendungen ist diese Definition vorzuziehen, da sie probabilistische Turing -Maschinen nicht erwähnt.

Verwandte Komplexitätsklassen

Diagram of randomised complexity classes
RP in Bezug auf andere probabilistische Komplexitätsklassen (Zpp, Co-RP, BPP, BQP, Pp), die verallgemeinern P innerhalb PSPACE. Es ist unbekannt, ob eine dieser Eindämme streng ist.

Die Definition von RP Sagt, dass ein Ja-Antwort immer Recht hat und dass ein No-Antwort möglicherweise falsch sein könnte, da ein Ja-Instanz einen No-Antwort zurückgeben kann. Die Komplexitätsklasse Co-RP ist das Komplement, bei dem ein Ja-Antwort möglicherweise falsch ist, während ein No-Antwort immer Recht hat.

Die Klasse BPP beschreibt Algorithmen, die sowohl auf Ja- als auch für keine Instanzen falsche Antworten geben können, und enthält somit beide RP und Co-RP. Der Schnittpunkt der Sets RP und Co-RP wird genannt Zpp. Genauso wie RP kann genannt werden REinige Autoren verwenden den Namen Co-R statt Co-RP.

Verbindung zu P und NP

Ungelöstes Problem in der Informatik:

P ist eine Teilmenge von RP, was eine Teilmenge von ist Np. Ähnlich, P ist eine Teilmenge von Co-RP Welches ist eine Untergruppe von Co-NP. Es ist nicht bekannt, ob diese Einschlüsse streng sind. Wenn jedoch die allgemein angenommene Vermutung P = BPP ist dann wahr, dann RP, Co-RP, und P Zusammenbruch (sind alle gleich). Vorausgesetzt, zusätzlich das PNpDies impliziert das dann RP ist streng enthalten in Np. Es ist nicht bekannt, ob RP = Co-RP, oder ob RP ist eine Untergruppe des Schnittpunkts von Np und Co-NP, obwohl dies durch impliziert würde durch P = BPP.

Ein natürliches Beispiel für ein Problem in Co-RP Derzeit nicht bekannt ist in P ist PolynomidentitätstestsDas Problem der Entscheidung, ob eine gegebene multivariate arithmetische Expression über die Ganzzahlen die Nullpolynom ist. Zum Beispiel, x·xy·y - (x + y) · (xy) ist das Nullpolynom, währendx·x + y·y ist nicht.

Eine alternative Charakterisierung von RP Das ist manchmal einfacher zu bedienen ist die Reihe von Problemen, die durch erkennbar sind Nichtdeterministische Turing -Maschinen Wenn die Maschine nur dann akzeptiert, ob und mindestens ein konstanter Teil der Berechnungspfade, unabhängig von der Eingangsgröße, akzeptieren. Np Andererseits benötigt nur einen akzeptierenden Weg, der einen exponentiell kleinen Teil der Pfade darstellen könnte. Diese Charakterisierung macht die Tatsache, dass RP ist eine Teilmenge von Np offensichtlich.

Siehe auch

Verweise

  1. ^ Dieser Vergleich wird auf Michael O. Rabin auf P. 252 von Gasarch, William (2014), "Probleme in Komplexitätsklassen klassifizieren", in Memon, Atif (Hrsg.), Fortschritte in Computern, Vol. 95 (PDF), Academic Press, S. 239–292.

Externe Links