Konkretes Verständnis des Unterschieds zwischen PP- und BPP -Definitionen

Question

Ich bin verwirrt darüber, wie Pp und BPP sind festgelegt. Nehmen wir an, $ chi $ ist die charakteristische Funktion für eine Sprache $ mathcal {l} $. M Sei die probabilistische Turing -Maschine. Sind die folgenden Definitionen korrekt:
$ Bpp = { mathcal {l}: pr [ chi (x) ne m (x)] geq frac {1} {2} + epsilon quad forall x in mathcal {l} epsilon> 0 } $
$ Pp = { mathcal {l}: pr [ chi (x) ne m (x)]> frac {1} {2} } $

Wenn die Definition falsch ist, versuchen Sie bitte, minimale Änderungen vorzunehmen, um sie zu korrigieren (dh keine andere äquivalente Definition, die die Zählmaschine oder ein geändertes Modell verwenden). Ich kann die Bedingungen für die Wahrscheinlichkeit bei beiden Definitionen nicht richtig unterscheiden.

Einige konkrete Beispiele mit klaren Einblicken in die subtilen Punkte wären sehr hilfreich.

Answer 1

Das sieht für mich richtig aus. Der Unterschied zwischen BPP und PP besteht darin, dass für BPP die Wahrscheinlichkeit größer als 1/2 $ betragen muss durch eine Konstante, während es für PP $ 1/2+ 1/2^n $ betragen könnte. Bei BPP -Problemen können Sie also eine Wahrscheinlichkeitsverstärkung mit einer kleinen Anzahl von Wiederholungen durchführen, während Sie für allgemeine PP -Probleme nicht können.

Answer 2

Die Antwort von VOR gibt die Standarddefinition an. Lassen Sie mich versuchen, den Unterschied etwas intuitiver zu erklären.

Sei $ m $ ein begrenzter Fehler probabilistischer Polynomzeitalgorithmus für eine Sprache $ l $, die mit der Wahrscheinlichkeit korrekt antwortet, mindestens $ p geq frac {1} {2}+ delta $. Sei $ x $ der Input und $ n $ die Größe des Eingangs.

Was einen beliebigen $ mathsf {pp} $ algorithmus aus einem $ mathsf {BPP} $ Algorithmus ist, ist das Positive Lücke Zwischen der Wahrscheinlichkeit, $ x in L $ zu akzeptieren, und der Wahrscheinlichkeit, $ x notin l $ zu akzeptieren. Das Wesentliche an $ mathsf {bpp} $ ist, dass die Lücke mindestens $ n^{-o (1)} $ ist. Ich werde versuchen zu erklären, warum diese Unterscheidung von Bedeutung ist und es uns ermöglicht, $ mathsf {bpp} $ als effiziente Algorithmen (sogar vermutet zu betrachten, als gleich $ mathsf {p} $) angesehen werden, während $ mathsf {pp} $ wird als ineffizient angesehen (eigentlich $ mathsf {pp} $ enthält $ mathsf {np} $). All dies kommt von dieser Lücke.

Schauen wir uns zunächst $ mathsf {pp} $ sorgfältiger an.

Beachten Sie, dass ein Algorithmus während seiner Ausführung höchsten Zufällige Bits, die den Algorithmus falsch antworten lassen.

Darüber hinaus kann ein Algorithmus mit Laufzeit $ t (n) $ nicht mehr als $ t (n) $ Random Bits verwenden.

Mit einem ähnlichen Argument können wir zeigen, dass der Fall, in dem der Unterschied zwischen der Wahrscheinlichkeit, ein $ x in L $ zu akzeptieren haben fast keinen Unterschied wie in $ mathsf {pp} $ case.

Bewegen wir uns nun auf $ mathsf {bpp} $.

Bei probabilistischen Algorithmen können wir die Wahrscheinlichkeit für die korrekte Beantwortung steigern. Nehmen wir an, wir möchten die Wahrscheinlichkeit der Richtigkeit auf 1- Epsilon $ für Fehlerwahrscheinlichkeit $ epsilon = 2^{-N} $ (exponentiell kleiner Fehler) erhöhen.

Die Idee ist einfach: Führen Sie mehrmals $ M $ und nehmen Sie die Antwort der Mehrheit.

Wie oft sollten wir $ M $ ausführen, um die Fehlerwahrscheinlichkeit für höchstens $ epsilon $ zu erhalten? $ Theta ( delta^{-1} lg epsilon) $ mal. Der Beweis ist am Ende dieser Antwort angegeben.

Lassen Sie uns nun die Überlegung übernehmen, dass die Algorithmen, die wir diskutieren, Polynomzeit sein müssen. Das bedeutet, dass wir nicht mehr als polynomial $ M $ laufen können. Mit anderen Worten, $ theta ( delta^{-1} ln epsilon) = n^{o (1)} $ oder einfacher einfacher

$$ delta^{-1} lg epsilon = n^{o (1)} $$

Diese Beziehung kategorisiert den begrenzten Fehler probabilistischer Algorithmen in Klassen in Abhängigkeit von ihrer Fehlerwahrscheinlichkeit. Es gibt keinen Unterschied zwischen der Fehlerwahrscheinlichkeit $ epsilon $ ist $ 2^{-n} $ oder eine positive Konstante (dh sich nicht mit $ n $) oder $ frac {1} {2} -n^{ O (1)} $. Wir können von einem von ihnen zu den anderen gelangen, während wir in der Polynomzeit bleiben.

Wenn $ delta $ zu klein ist, sagen wir $ 0 $, $ 2^{-n} $ oder sogar $ n^{- Omega (1)} $, haben wir keine Möglichkeit, die Wahrscheinlichkeit der Richtigkeit zu steigern und Reduzierung der Fehlerwahrscheinlichkeit ausreichend, um in $ mathsf {BPP} $ einzusteigen.

Der Hauptpunkt hier ist, dass wir in $ Mathsf {BPP} $ die Fehlerwahrscheinlichkeit exponentiell reduzieren können, sodass wir uns über die Antworten fast sicher sind, und das lässt uns diese Klasse von Algorithmen als effiziente Algorithmen betrachten. Die Fehlerwahrscheinlichkeit kann so stark reduziert werden, dass ein Hardwarefehler wahrscheinlicher ist oder sogar ein Meteor, der auf den Computer fällt, eher einen Fehler durch den probabilistischen Algorithmus macht.

Das gilt nicht für $ mathsf {pp} $, wir wissen keine Möglichkeit, die Fehlerwahrscheinlichkeit zu reduzieren, und wir sind übrig fast Als ob wir antworten, indem wir eine Münze werfen, um die Antwort zu erhalten (wir sind nicht vollständig, sind die Wahrscheinlichkeiten nicht halb und halb, aber sie ist sehr nahe an dieser Situation).

---

In diesem Abschnitt wird der Beweis angegeben, dass die Fehlerwahrscheinlichkeit $ epsilon $ Wenn wir mit einem Algorithmus mit Gap $ beginnen ( frac {1} {2}- delta, frac {1} {2}+ delta) $ We Sollte $ m $ $ theta ( delta^{-1} lg epsilon) $ mal ausgeführt werden.

Sei $ n_k $ der Algorithmus, der $ M $ für $ k $ -mal läuft und dann gemäß der Antwort der Mehrheit antwortet. Nehmen wir zum Einfachheit halber an, dass $ K $ seltsam ist, sodass wir keine Krawatten haben.

Betrachten Sie den Fall, dass $ x in l $. Der Fall $ x notin l $ ist ähnlich. Dann $$ mathsf {pr} {m (x) text {akzeptiert} } = p geq frac {1} {2} + delta $$, um die Richtigkeitswahrscheinlichkeit von $ n_k $ zu analysieren, müssen wir müssen Schätzen Sie die Wahrscheinlichkeit, dass die Mehrheit der K $ K $ -Räufe akzeptiert.

Sei $ x_i $ 1, wenn der $ i $ th run akzeptiert und $ 0 $ ist, wenn es ablehnt. Beachten Sie, dass jeder Lauf von anderen unabhängig ist, da sie unabhängige Zufallsbits verwenden. So sind $ x_i $ s unabhängige boolesche zufällige Variablen, wobei $$ mathbb {e} [x_i] = mathsf {pr} {x_i = 1 } = mathsf {pr} {m (x) text {Akzeptiert } } = p geq frac {1} {2}+ delta $$

Sei $ y = sigma_ {i = 1}^k x_i $. Wir müssen die Wahrscheinlichkeit schätzen, dass die Mehrheit akzeptiert, dh die Wahrscheinlichkeit, dass $ y geq frac {k} {2} $.

$$ mathsf {pr} {n_k (x) text {akzeptiert} } = mathsf {pr} {y geq frac {k} {2} } $$

Wie es geht? Wir können Chernoff Bound verwenden, was uns die Wahrscheinlichkeitskonzentration in der Nähe des erwarteten Werts zeigt. Für jede zufällige Variable $ z $ mit dem erwarteten Wert $ mu $ haben wir

$$ mathsf {pr} {| z- mu | > alpha mu } <e^{ frac { alpha^2} {4} mu} $$

Das besagt, dass die Wahrscheinlichkeit, dass $ z $ $ alpha mu $ weit von seinem erwarteten Wert $ mu $ ist, exponentiell abnimmt, wenn $ alpha $ erhöht wird. Wir werden es verwenden, um die Wahrscheinlichkeit von $ y < frac {k} {2} $ zu gebunden.

Beachten Sie, dass wir durch Linearität der Erwartung $$ mathbb {e} [y] = mathbb {e} [ sigma_ {i = 1}^k x_i] = sigma_ {i = 1}^k mathbb {e haben haben } [X_i] = kp geq frac {k} {2} + k delta $$

Jetzt können wir die Tschernoff -Grenze anwenden. Wir wollen eine Obergrenze für die Wahrscheinlichkeit von $ y < frac {k} {2} $. Die Tschernoff-Grenze gibt die Wahrscheinlichkeit von $ | y-( frac {k} {2}+k delta) | > K Delta $, was ausreichend ist. Wir haben

$$ pr {| y - kp | > alpha kp } <e^{- frac { alpha^2} {4} kp} $$

und wenn wir $ alpha $ so auswählen, dass $ alpha kp = k delta $ wir sind fertig, also wählen wir $ alpha = frac { delta} {p} leq frac {2 delta} {2 Delta+1} $.

Deshalb haben wir

$$ pr {y < frac {k} {2} } leq pr {| y - ( frac {k} {2}+k delta) | > k delta } leq pr {| y - kp | > alpha kp } <e^{- frac { alpha^2} {4} kp} $$

Und wenn Sie die Berechnungen durchführen, werden Sie das sehen

$$ frac { alpha^2} {4} kp leq frac { delta^2} {4 delta+2} k = theta (k delta) $$

wir haben

$$ pr {y < frac {k} {2} } <e^{- theta (k delta)} $$

Wir möchten, dass der Fehler höchstens $ Epsilon $ ist, also wollen wir

$$ e^{- theta (k delta)} leq epsilon $$

oder mit anderen Worten

$$ theta ( delta^{-1} lg epsilon) leq k $$

Ein wesentlicher Punkt hier ist, dass wir dabei viel mehr zufällige Bits verwenden werden und auch die Laufzeit steigt. Der dh die Worst-Case-Laufzeit von $ n_k $ wird ungefähr k $ -Ffache der Laufzeit von $ m betragen $.

Hier war der mittlere Punkt der Lücke $ frac {1} {2} $. Aber im Allgemeinen muss dies nicht der Fall sein. Wir können eine ähnliche Methode für andere Werte anwenden, indem wir andere Fraktionen anstelle der Mehrheit zum Akzeptieren einnehmen.

Answer 3

Verwenden Sie Ihre Notation:

$ Bpp = {l: existiert $ a probabilistisches Polynom-Zeit-Turing-Maschine $ m, $ und ein koststoff $ 0 <c leq 1/2 $, so dass $ forall x ; Pr [ chi_l (x) = m (x)] geq frac {1} {2} + c } $

$ Pp = {l: existiert $ eine probabilistische Polynom-Zeit-Turing-Maschine $ m $ so, dass $ forall x ; Pr [ chi_l (x) = m (x)]> frac {1} {2} } $

Der Unterschied wurde von Adriann darauf hingewiesen, und Sie können sich auch Wikipedia ansehen PP gegen BPP