ZPP (Komplexität)

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

Im Komplexitätstheorie, Zpp (Null-Irrtum probabilistisch Polynomzeit) ist der Komplexitätsklasse von Problemen, für die a Probabilistische Turing -Maschine existiert mit diesen Eigenschaften:

  • Es gibt immer das richtige Ja oder Nein -Antwort zurück.
  • Die Laufzeit ist polynomisch in der Erwartung für jeden Eingang.

Mit anderen Worten, wenn der Algorithmus während des Laufens eine wirklich randomische Münze drehen darf, wird er immer die richtige Antwort und für ein Problem der Größe zurückgeben nEs gibt ein Polynom p(n) so dass die durchschnittliche Laufzeit kleiner als p(n), obwohl es gelegentlich viel länger sein mag. Ein solcher Algorithmus wird a genannt Las Vegas Algorithmus.

Alternative, Zpp kann definiert als die Klasse von Problemen, für die a Probabilistische Turing -Maschine existiert mit diesen Eigenschaften:

  • Es läuft immer in Polynomzeit.
  • Es gibt eine Antwort zurück. Ja, nein oder weiß es nicht.
  • Die Antwort ist immer entweder nicht bekannt oder die richtige Antwort.
  • Es kennt sich nicht mit der Wahrscheinlichkeit für jeden Eingang (und ansonsten die richtige Antwort).

Die beiden Definitionen sind gleichwertig.

Die Definition von Zpp basiert auf probabilistischen Turing -Maschinen, beachten Sie jedoch, dass andere Komplexitätsklassen basierend auf ihnen enthalten BPP und RP. Die Klasse BQP basiert auf einer anderen Maschine mit Zufälligkeit: die Quantencomputer.

Kreuzungsdefinition

Die Klasse Zpp ist genau gleich dem Schnittpunkt der Klassen RP und Co-RP. Dies wird oft als Definition von angesehen Zpp. Um dies zu zeigen, beachten Sie zunächst, dass jedes Problem, das sich befindet beide RP und Co-RP hat ein Las Vegas Algorithmus folgendermaßen:

  • Angenommen, wir haben eine Sprache, die von beiden erkannt wurde RP Algorithmus A und die (möglicherweise völlig anders) Co-RP Algorithmus B.
  • Führen Sie bei einem Eingang einen Schritt auf dem Eingang aus. Wenn es ja zurückgibt, muss die Antwort ja sein. Andernfalls führen Sie B für einen Schritt auf die Eingabe aus. Wenn es nein zurückgibt, darf die Antwort nein sein. Wenn keiner auftritt, wiederholen Sie diesen Schritt.

Beachten Sie, dass nur eine Maschine jemals eine falsche Antwort geben kann und die Wahrscheinlichkeit, dass diese Maschine während jeder Wiederholung die falsche Antwort gibt, höchstens 50%. Dies bedeutet, dass die Chance, die zu erreichen kDie Runde schrumpft exponentiell in k, zeigen, dass die erwartet Laufzeit ist Polynom. Dies zeigt, dass RP schneiden Co-RP ist in Zpp.

Zu zeigen, dass Zpp ist in RP schneiden Co-RPAngenommen, wir haben einen Las Vegas -Algorithmus C, um ein Problem zu lösen. Wir können dann Folgendes erstellen RP Algorithmus:

  • Laufen Sie C für zumindest doppelt Es ist erwartet. Wenn es eine Antwort gibt, geben Sie diese Antwort. Wenn es keine Antwort gibt, bevor wir es stoppen, geben Sie nein.

Durch Markovs Ungleichheit, Die Chance, dass es eine Antwort liefert, bevor wir sie stoppen, ist mindestens 1/2. Dies bedeutet die Chance, dass wir die falsche Antwort auf eine Ja -Instanz geben, indem wir nein, höchstens 1/2, die Definition eines anpasst RP Algorithmus. Das Co-RP Der Algorithmus ist identisch, außer dass es Ja gibt, wenn C "ausgeht".

Zeugen und Beweis

Die Klassen Np, RP und Zpp kann in einem Set im Hinblick auf den Beweis für die Mitgliedschaft betrachtet werden.

Definition: A Überprüfung V für ein Satz X ist eine Turing -Maschine, so dass:

  • wenn x ist in X Dann gibt es eine Zeichenfolge w so dass V(x,w) akzeptiert;
  • wenn x ist nicht in Xdann für alle Saiten w, V(x,w) lehnt ab.

Die Saite w kann als Beweis für die Mitgliedschaft betrachtet werden. Bei kurzen Beweisen (von Länge, die durch ein Polynom in der Größe des Eingangs begrenzt sind), die effizient verifiziert werden können (V ist eine polynomiale deterministische Turing-Maschine), die Zeichenfolge w wird als a genannt Zeuge.

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 Saiten, von denen keiner ein Beweis für die Mitgliedschaft ist.
  • Die Verfügbarkeit von Zeugen ist einheitlich. Für alle x in x muss es einen Zeugen geben. Es ist nicht der Fall, in dem bestimmte x in x zu schwierig zu überprüfen sind, während die meisten nicht sind.
  • Der Zeuge muss kein traditionell ausgelegter Beweis sein. Wenn V eine probabilistische Turing -Maschine ist, die möglicherweise x akzeptieren könnte, wenn x in x ist, ist der Beweis die Reihe von Münzflips, die die Maschine durch Glück, Intuition oder Genie zum Akzeptieren führt x.
  • Das Co-Concept ist ein Beweis für Nichtmitglieder oder Mitgliedschaft in der Komplement-Set.

Die Klassen Np, RP und Zpp sind Sätze, die Zeugen für die Mitgliedschaft haben. Die Klasse Np erfordert nur, dass Zeugen existieren. Sie können sehr selten sein. Der 2f(|x|) mögliche Saiten mit f Ein Polynom, nur ein Bedarf, führt dazu, dass der Überprüfer akzeptiert wird (wenn x in X ist. Wenn x nicht in x ist, wird kein String der Überprüfer akzeptiert).

Für die Klassen RP und Zpp Jede zufällig ausgewählte Zeichenfolge wird wahrscheinlich ein Zeuge sein.

Die entsprechenden Co-Klassen haben Zeugen für Nichtmitglieder. Im Speziellen, Co-RP ist die Klasse der Sätze, für die, wenn x nicht in x ist, eine zufällig ausgewählte Zeichenfolge wahrscheinlich ein Zeuge für Nichtmitglieder ist. Zpp ist die Klasse von Sätzen, für die eine zufällige Zeichenfolge wahrscheinlich ein Zeuge von x in x oder x in x ist, was jemals der Fall sein kann.

Verbinden dieser Definition mit anderen Definitionen von RP, Co-RP und Zpp ist einfach. Die probabilistische Polynom-Zeit-Turing-Maschine V*w(x) entspricht der deterministischen Polynom-Zeit-Turing-Maschine V(x, w) durch Ersetzen des zufälligen Bandes von V* Mit einem zweiten Eingangsband für V, auf dem die Abfolge von Münzflips geschrieben wird. Durch die Auswahl des Zeugen als zufällige Zeichenfolge ist der Überprüfer eine probabilistische Polynom-Zeit-Turing-Maschine, deren Wahrscheinlichkeit, x zu akzeptieren, wenn x ist in X ist groß (größer als 1/2, sagen wir), aber Null, wenn xX (zum RP); von abzulehnen x, wenn x nicht in x ist, ist groß, aber Null, wenn xX (zum Co-RP); und richtig zu akzeptieren oder abzulehnen x als Mitglied von X ist groß, aber null fälschlicherweise akzeptiert oder ablehnt x (für Zpp).

Durch wiederholte zufällige Auswahl eines möglichen Zeugen gibt die große Wahrscheinlichkeit, dass ein zufälliger Zeichenfolge ein Zeuge ist, einen erwarteten Polynomzeitalgorithmus für die Annahme oder Ablehnung eines Eingangs. Wenn die Turing-Maschine umgekehrt eine Polynomzeit erwartet wird (für ein bestimmtes x), muss ein beträchtlicher Teil der Läufe die Polynomzeit begrenzt sein, und die in einem solchen Lauf verwendete Münzsequenz wird ein Zeuge sein.

Zpp sollte im Gegensatz zu im Gegensatz zu werden BPP. Die Klasse BPP erfordert keine Zeugen, obwohl Zeugen ausreichend sind (daher BPP enthält RP, Co-RP und Zpp). EIN BPP Die Sprache hat V (x, w) Akzeptieren auf eine (klare) Mehrheit der Saiten w, wenn x in x ist, und lehnt umgekehrt auf eine (klare) Mehrheit der Saiten w ab, wenn x nicht in ist X. Keine einzelne Zeichenfolge, muss endgültig sein, und daher können sie im Allgemeinen nicht als Beweise oder Zeugen angesehen werden.

Komplexitätstheoretische Eigenschaften

Es ist bekannt, dass ZPP unter Komplement geschlossen ist; Das heißt, ZPP = Co-ZPP.

ZPP ist niedrig Für sich selbst, was bedeutet, dass eine ZPP -Maschine mit der Leistung, ZPP -Probleme sofort (eine ZPP -Oracle -Maschine), ohne diese zusätzliche Leistung nicht leistungsfähiger ist als die Maschine. In Symbolen, ZppZpp = Zpp.

ZppNpBPP = ZppNp.

NpBPP ist in ZppNp.

Verbindung zu anderen Klassen

Seit Zpp = RPLeiche, Zpp ist offensichtlich in beiden enthalten RP und Leiche.

Die Klasse P ist in Zppund einige Informatiker haben das vermutet P = Zpp, d.h. jeder Las Vegas-Algorithmus hat ein deterministisches Polynom-Zeit-Äquivalent.

Es gibt ein Orakel, das relativ zu welchem ​​vorhanden ist Zpp = Nachfolger. Ein Beweis für Zpp = Nachfolger würde das bedeuten PZpp, wie PNachfolger (sehen Zeithierarchie Theorem).

Siehe auch

Externe Links