ZPP (Komplexität) - ZPP (complexity)
In der Komplexitätstheorie ist ZPP (Zero-Error Probabilistic Polynomial Time ) die Komplexitätsklasse von Problemen, für die eine probabilistische Turing-Maschine mit folgenden Eigenschaften existiert:
- Es wird immer die richtige JA- oder NEIN-Antwort zurückgegeben.
- Die Laufzeit ist in Erwartung für jede Eingabe polynomisch.
Mit anderen Worten, wenn der Algorithmus eine wirklich zufällige Münze werfen darf, während er läuft, gibt er immer die richtige Antwort zurück, und für ein Problem der Größe n gibt es ein Polynom p ( n ), so dass der Durchschnitt läuft Die Zeit wird kürzer als p ( n ) sein, obwohl sie gelegentlich viel länger sein kann. Ein solcher Algorithmus wird als Las Vegas-Algorithmus bezeichnet .
Alternativ kann ZPP als die Klasse von Problemen definiert werden, für die eine probabilistische Turing-Maschine mit folgenden Eigenschaften existiert:
- Es läuft immer in Polynomzeit.
- Es wird eine Antwort zurückgegeben: JA, NEIN oder NICHT WISSEN.
- Die Antwort ist immer entweder entweder NICHT WISSEN oder die richtige Antwort.
- Es gibt DO NOT KNOW mit einer Wahrscheinlichkeit von höchstens 1/2 für jede Eingabe zurück (und ansonsten die richtige Antwort).
Die beiden Definitionen sind äquivalent.
Die Definition von ZPP basiert auf probabilistischen Turing-Maschinen. Beachten Sie jedoch aus Gründen der Klarheit, dass andere darauf basierende Komplexitätsklassen BPP und RP umfassen . Die Klasse BQP basiert auf einer anderen Maschine mit Zufälligkeit: dem Quantencomputer .
Schnittpunktdefinition
Die Klasse ZPP ist genau gleich dem Schnittpunkt der Klassen RP und Co-RP . Dies wird oft als Definition von ZPP angesehen . Um dies zu zeigen, beachten Sie zunächst, dass jedes Problem, das sowohl in RP als auch in Co-RP auftritt, einen Las Vegas-Algorithmus wie folgt hat:
- Angenommen, wir haben eine Sprache L, die sowohl vom RP- Algorithmus A als auch vom (möglicherweise völlig anderen) Co-RP- Algorithmus B erkannt wird .
- Führen Sie bei einer gegebenen Eingabe A für einen Schritt auf der Eingabe aus. Wenn es JA zurückgibt, muss die Antwort JA sein. Andernfalls führen Sie B für einen Schritt am Eingang aus. Wenn NEIN zurückgegeben wird, muss die Antwort NEIN sein. Wenn beides nicht auftritt, wiederholen Sie diesen Schritt.
Beachten Sie, dass nur eine Maschine jemals eine falsche Antwort geben kann und die Wahrscheinlichkeit, dass diese Maschine bei jeder Wiederholung die falsche Antwort gibt, höchstens 50% beträgt. Dies bedeutet, dass die Chance, die k- te Runde zu erreichen, in k exponentiell abnimmt , was zeigt, dass die erwartete Laufzeit polynomisch ist. Dies zeigt, dass RP- Schnittpunkt- Co-RP in ZPP enthalten ist .
Angenommen, wir haben einen Las Vegas-Algorithmus C, um ein Problem zu lösen, um zu zeigen, dass ZPP in RP- Schnitt- Co-RP enthalten ist. Wir können dann den folgenden RP- Algorithmus konstruieren :
- Führen Sie C mindestens doppelt so lange wie erwartet aus. Wenn es eine Antwort gibt, geben Sie diese Antwort. Wenn es keine Antwort gibt, bevor wir es stoppen, geben Sie NEIN.
Durch Markovs Ungleichung beträgt die Wahrscheinlichkeit, dass es eine Antwort gibt, bevor wir damit aufhören, mindestens 1/2. Dies bedeutet, dass die Wahrscheinlichkeit, dass wir auf einer YES-Instanz die falsche Antwort geben, indem wir NO stoppen und ausgeben, höchstens 1/2 beträgt, was der Definition eines RP- Algorithmus entspricht. Der Co-RP- Algorithmus ist identisch, außer dass er JA gibt, wenn C "Zeitüberschreitung" aufweist.
Zeugnis und Beweis
Die Klassen NP , RP und ZPP können als Nachweis der Mitgliedschaft in einem Set betrachtet werden.
Definition: Ein Prüfer V für eine Menge X ist eine Turing-Maschine, so dass:
- Wenn x in X ist, existiert eine Zeichenkette w, so dass V ( x , w ) akzeptiert;
- wenn x nicht in X , dann für alle Saiten W , V ( x , w ) Spuck.
Die Zeichenfolge w kann als Nachweis der Mitgliedschaft angesehen werden. Bei kurzen Beweisen (deren Länge durch ein Polynom in der Größe der Eingabe begrenzt ist), die effizient verifiziert werden können ( V ist eine deterministische Turing-Maschine mit Polynomzeit), wird die Zeichenfolge w als Zeuge bezeichnet .
Anmerkungen:
- Die Definition ist sehr asymmetrisch. Der Beweis, dass x in X ist, ist eine einzelne Zeichenfolge. Der Beweis, dass x nicht in X ist, ist die Sammlung aller Zeichenfolgen, von denen keine ein Mitgliedschaftsnachweis ist.
- Die Verfügbarkeit von Zeugen ist einheitlich. Für alle x in X muss es einen Zeugen geben. Es ist nicht der Fall, dass bestimmte x in X zu schwer zu überprüfen sind, während die meisten dies nicht tun.
- Der Zeuge muss kein traditionell aufgestellter Beweis sein. Wenn V eine probabilistische Turing-Maschine ist, die möglicherweise x akzeptieren könnte, wenn x in X ist, dann ist der Beweis die Folge von Münzwürfen, die die Maschine durch Glück, Intuition oder Genie dazu bringt, x zu akzeptieren .
- Das Co-Konzept ist ein Beweis für die Nichtmitgliedschaft oder die Mitgliedschaft im Komplementsatz.
Die Klassen NP , RP und ZPP sind Sets, die Zeugen für die Mitgliedschaft haben. Die Klasse NP verlangt nur, dass Zeugen existieren. Sie können sehr selten sein. Von den 2 f (| x |) möglichen Zeichenfolgen mit f als Polynom muss nur eine den Verifizierer akzeptieren lassen (wenn x in X ist. Wenn x nicht in X ist, bewirkt keine Zeichenfolge, dass der Verifizierer akzeptiert).
Für die Klassen RP und ZPP ist wahrscheinlich jede zufällig ausgewählte Zeichenfolge ein Zeuge.
Die entsprechenden Co-Klassen haben Zeugnis für die Nichtmitgliedschaft. Insbesondere ist co-RP die Klasse von Mengen, für die, wenn x nicht in X ist, jede zufällig ausgewählte Zeichenfolge wahrscheinlich ein Zeuge für die Nichtmitgliedschaft ist. ZPP ist die Klasse von Mengen, für die jede zufällige Zeichenfolge wahrscheinlich Zeuge von x in X oder x nicht in X ist, je nachdem, was der Fall sein mag.
Das Verbinden dieser Definition mit anderen Definitionen von RP , Co-RP und ZPP ist einfach. Die probabilistische Polynomzeit-Turingmaschine V * w ( x ) entspricht der deterministischen Polynomzeit-Turingmaschine V ( x , w ), indem das Zufallsband von V * durch ein zweites Eingabeband für V ersetzt wird, auf das die Folge von geschrieben ist Münzwürfe. Durch Auswahl des Zeugen als zufällige Zeichenfolge ist der Verifizierer eine probabilistische Polynomzeit-Turingmaschine, deren Wahrscheinlichkeit, x zu akzeptieren, wenn x in X ist, groß ist (z. B. größer als 1/2), aber Null, wenn x ∉ X ist (für RP) ); x abzulehnen, wenn x nicht in X ist, ist groß, aber Null, wenn x ∈ X ist (für Co-RP ); und das korrekte Akzeptieren oder Ablehnen von x als Mitglied von X ist groß, aber Null des falschen Akzeptierens oder Ablehnens von x (für ZPP ).
Durch wiederholte zufällige Auswahl eines möglichen Zeugen ergibt die große Wahrscheinlichkeit, dass eine zufällige Zeichenfolge ein Zeuge ist, einen erwarteten Polynomzeitalgorithmus zum Akzeptieren oder Ablehnen einer Eingabe. Wenn umgekehrt für die Turing-Maschine eine Polynomzeit (für ein gegebenes x) erwartet wird, muss ein beträchtlicher Teil der Läufe polynomzeitbegrenzt sein, und die in einem solchen Lauf verwendete Münzsequenz ist ein Zeuge.
ZPP sollte mit BPP verglichen werden . Die Klasse BPP benötigt keine Zeugen, obwohl Zeugen ausreichend sind (daher enthält BPP RP , Co-RP und ZPP ). In einer BPP- Sprache akzeptiert V (x, w) eine (klare) Mehrheit der Zeichenfolgen w, wenn x in X ist, und lehnt umgekehrt eine (klare) Mehrheit der Zeichenfolgen w ab, wenn x nicht in X ist . Keine einzelne Zeichenfolge muss endgültig sein, und daher können sie im Allgemeinen nicht als Beweise oder Zeugen betrachtet werden.
Komplexitätstheoretische Eigenschaften
Es ist bekannt, dass ZPP unter Komplement geschlossen ist; das heißt, ZPP = Co-ZPP.
ZPP ist für sich selbst niedrig , was bedeutet, dass eine ZPP-Maschine mit der Fähigkeit, ZPP-Probleme sofort zu lösen (eine ZPP-Orakelmaschine), nicht leistungsfähiger ist als die Maschine ohne diese zusätzliche Leistung. In Symbolen ist ZPP ZPP = ZPP .
ZPP NP BPP = ZPP NP .
NP BPP ist in ZPP NP enthalten .
Verbindung zu anderen Klassen
Da ZPP = RP ∩ coRP , ZPP ist offensichtlich in beiden enthalten RP und coRP .
Die Klasse P ist in ZPP enthalten , und einige Informatiker haben vermutet, dass P = ZPP ist , dh jeder Las Vegas-Algorithmus hat ein deterministisches Polynom-Zeit-Äquivalent.
Es gibt ein Orakel, zu dem ZPP = EXPTIME gehört . Ein Beweis für ZPP = EXPTIME würde bedeuten, dass P ≠ ZPP als P ≠ EXPTIME gilt (siehe Zeithierarchiesatz ).