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

• Es gibt immer das richtige JA oder KEINE Antwort zurück.
• Die Laufzeit ist Polynom der en general für jeden Eingang.

Mit anderen Worten wird dem Algorithmus erlaubt, eine aufrichtig zufällige Münze zu schnipsen, während er läuft. Es gibt immer die richtige Antwort zurück. (Solch ein Algorithmus wird einen Las Vegas Algorithmus genannt.) Für ein Problem der Größe n gibt es ein Polynom p (n) solch, dass die durchschnittliche Laufzeit weniger sein wird als p (n), wenn auch es gelegentlich viel länger sein könnte.

Wechselweise kann ZPP als die Klasse von Problemen definiert werden, für die eine probabilistic Maschine von Turing mit diesen Eigenschaften besteht:

• Es läuft immer in der polynomischen Zeit.
• Es gibt eine Antwort JA, NICHT zurück, oder NICHT WISSEN.
• Die Antwort ist entweder WISSEN SIE immer NICHT oder die richtige Antwort.
• Wenn die richtige Antwort ist JA, dann gibt sie JA mit der Wahrscheinlichkeit mindestens 1/2 zurück (und WISSEN SIE sonst NICHT).
• Wenn die richtige Antwort ist Nein, dann kehrt sie NICHT mit der Wahrscheinlichkeit mindestens 1/2 zurück (und WISSEN SIE sonst NICHT).

Die zwei Definitionen sind gleichwertig.

Die Definition von ZPP basiert auf probabilistic Maschinen von Turing. Andere auf ihnen gestützte Kompliziertheitsklassen schließen BPP und RP ein. Die Klasse BQP basiert auf einer anderen Maschine mit der Zufälligkeit: der Quant-Computer.

Kreuzungsdefinition

Die Klasse ZPP ist der Kreuzung der Klassen RP und HANDELSGESELLSCHAFT genau gleich. Das wird häufig genommen, um die Definition von ZPP zu sein. Um das zu zeigen, bemerken Sie zuerst, dass jedes Problem, das sowohl in RP als auch in Handelsgesellschaft ist, einen Las Vegas Algorithmus wie folgt hat:

• Nehmen Sie an, dass wir eine Sprache L anerkannt sowohl durch den RP Algorithmus A als auch durch (vielleicht völlig verschieden) Handelsgesellschaft-Algorithmus B haben.
• In Anbetracht eines Eingangs in L, geführt auf dem Eingang. Wenn es zurückkehrt, JA, muss die Antwort JA sein. Sonst, geführter B auf dem Eingang. Wenn es zurückkehrt, Nein, muss die Antwort NEIN sein. Wenn keiner vorkommt, wiederholen Sie diesen Schritt.

Bemerken Sie, dass nur eine Maschine jemals eine falsche Antwort geben kann, und die Chance dieser Maschine, die die falsche Antwort während jeder Wiederholung gibt, an den meisten 50 % ist. Das bedeutet, dass die Chance, den kth zu erreichen, herum exponential in k zurückweicht, zeigend, dass die erwartete Laufzeit Polynom ist. Das zeigt, dass sich RP schneiden, wird Handelsgesellschaft in ZPP enthalten.

Um zu zeigen, dass ZPP in RP enthalten wird, schneiden Handelsgesellschaft durch, nehmen an, dass wir einen Las Vegas Algorithmus C haben, um ein Problem zu beheben. Wir können dann den folgenden RP Algorithmus bauen:

• Geführte C dafür verdoppeln mindestens seine erwartete Laufzeit. Wenn es eine Antwort gibt, geben Sie diese Antwort. Wenn es keine Antwort gibt, bevor wir es aufhören, NEIN geben.

Durch die Ungleichheit von Markov die Chance, dass es eine Antwort nachgeben wird, bevor wir anhalten, ist es 1/2. Das bedeutet die Chance, die wir der falschen Antwort auf JA geben werden, der Beispiel, durch das Aufhören und das Tragen Nein, nur 1/2 ist, die Definition eines RP Algorithmus passend. Der Handelsgesellschaft-Algorithmus ist identisch, außer dass er JA wenn C "Zeiten" gibt.

Zeuge und Beweis

Von den Klassen NP, RP und ZPP kann in Bezug auf den Beweis der Mitgliedschaft in einem Satz gedacht werden.

Definition: Ein verifier V für einen Satz X ist eine solche Maschine von Turing dass:

• wenn x in X dann ist, dort besteht eine Schnur w solch, dass V (x, w) akzeptiert;
• wenn x nicht in X ist, dann für alle Schnuren w, V (x, w) weist zurück.

Von der Schnur w kann als der Beweis der Mitgliedschaft gedacht werden. Im Fall von kurzen Beweisen (der Länge, die durch ein Polynom in der Größe des Eingangs begrenzt ist), der effizient nachgeprüft werden kann (V ist eine polynomisch-malige deterministische Maschine von Turing), Schnur w Zeuge genannt.

Zeichen:

• Die Definition ist sehr asymmetrisch. Der Beweis von x, der in X ist, ist eine einzelne Schnur. Der Beweis von x, der nicht in X ist, ist die Sammlung aller Schnuren, von der keine ein Beweis der Mitgliedschaft ist.
• Die Verfügbarkeit des Zeugen ist gleichförmig. Für den ganzen x in X muss es einen Zeugen geben. Es ist nicht der Fall, wo sicher, x in X ist zu schwierig nachzuprüfen, wohingegen die meisten nicht sind.
• Der Zeuge braucht kein traditionell analysierter Beweis zu sein. Wenn V ein probabilisitic Turing Maschine ist, die möglich gekonnt hat, x akzeptieren, wenn x in X ist, dann ist der Beweis die Reihe von Münzflips, die die Maschine, durch das Glück, die Intuition oder das Genie, zum Annehmen x führt.
• Der co - Konzept ist ein Beweis der Nichtmitgliedschaft oder Mitgliedschaft im Ergänzungssatz.

Der Klassen-NP, RP und ZPP sind Sätze, die Zeugen für die Mitgliedschaft haben. Der Klassen-NP verlangt nur, dass Zeugen bestehen. Sie können sehr selten sein. Der 2 möglichen Schnuren, mit f ein Polynom, nur eine Bedürfnis-Ursache der verifier, um zu akzeptieren (wenn x in X ist. Wenn x nicht in X ist, wird keine Schnur den verifier veranlassen zu akzeptieren).

Für die Klassen RP und ZPP wird jede Schnur gewählt wahrscheinlich aufs Geratewohl ein Zeuge sein.

Die entsprechenden Co-Klassen haben Zeugen für die Nichtmitgliedschaft. Insbesondere Handelsgesellschaft ist die Klasse von Sätzen, für die wenn x nicht in X ist, wird jede zufällig gewählte Schnur wahrscheinlich ein Zeuge für die Nichtmitgliedschaft sein. ZPP ist die Klasse von Sätzen, für die jede zufällige Schnur wahrscheinlich ein Zeuge von x in X oder x nicht in X sein wird, der jemals der Fall sein kann.

Diese Definition mit anderen Definitionen von RP, Handelsgesellschaft und ZPP in Verbindung zu stehen, ist leicht. Der probablisitic polynomisch-malige Turing Machine V (x) entspricht dem deterministischen polynomisch-maligen Turing Machine V (x, w), indem er das zufällige Band V mit einem zweiten Eingangsband für V ersetzt, über den die Folge von Münzflips geschrieben wird. Durch das Auswählen des Zeugen als eine zufällige Schnur ist der verifier ein probabilistic polynomisch-maliger Turing Machine, dessen Wahrscheinlichkeit, x zu akzeptieren, wenn x in X ist, groß ist (größer als 1/2, sagen Sie), aber Null, wenn x nicht in X (für RP) ist; x zurückzuweisen, wenn x nicht in X ist, ist groß, aber Null, wenn x in X (für die Handelsgesellschaft) ist; und des richtigen Annehmens oder der Zurückweisung x weil ist ein Mitglied X, aber Null des falschen Annehmens oder der Zurückweisung x (für ZPP) groß.

Durch die wiederholte zufällige Auswahl an einem möglichen Zeugen gibt die große Wahrscheinlichkeit, dass eine zufällige Schnur ein Zeuge ist, einen erwarteten polynomischen Zeitalgorithmus, um einen Eingang zu akzeptieren oder zurückzuweisen. Umgekehrt, wenn die Turing Maschine polynomisch-malig erwartet wird (für irgendwelchen gegeben x), dann muss ein beträchtlicher Bruchteil der Läufe begrenzt sein polynomisch-malig, und die in solch einem Lauf verwendete Münzfolge wird ein Zeuge sein.

ZPP sollte mit BPP gegenübergestellt werden. Der Klassen-BPP verlangt Zeugen nicht, obwohl Zeugen genügend sind (folglich, enthält BPP RP, Handelsgesellschaft und ZPP). Eine BPP Sprache hat V (x, w) akzeptieren auf einer (klaren) Mehrheit von Schnuren w, wenn x in X ist, und weisen Sie umgekehrt auf einer (klaren) Mehrheit von Schnuren w zurück, wenn x nicht in X ist. Keine einzelne Schnur w muss endgültig sein, und deshalb können sie nicht als Beweise oder Zeugen im Allgemeinen betrachtet werden.

Verbindung zu anderen Klassen

Seit ZPP = RP  Handelsgesellschaft wird ZPP offensichtlich sowohl in RP als auch in Handelsgesellschaft enthalten.

Die Klasse P wird in ZPP enthalten, und einige Computerwissenschaftler haben vermutet, dass P = ZPP, d. h., jeder Las Vegas Algorithmus eine deterministische polynomisch-malige Entsprechung hat.

Ein Beweis für ZPP = würde EXPTIME (obwohl das fast sicher falsch ist) andeuten, dass P  ZPP, als P  EXPTIME (sieh Zeithierarchie-Lehrsatz).

Links