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

9

Ich bin verwirrt darüber, wie PP und BPP definiert sind. Nehmen wir an , ist die charakteristische Funktion für eine Sprache L . M ist die probabilistische Turingmaschine. Sind die folgenden Definitionen korrekt: B P P = { L : P r [ χ ( x ) M ( x ) ] 1χL
P P = { L : P r [ χ ( x ) M ( x ) ] > 1BPP={L:Pr[χ(x)M(x)]12+ϵxL, ϵ>0}
PP={L:Pr[χ(x)M(x)]>12}

Wenn die Definition falsch ist, versuchen Sie bitte, minimale Änderungen vorzunehmen, um sie zu korrigieren (dh geben Sie keine andere äquivalente Definition an, die eine Zählmaschine oder ein modifiziertes Modell verwendet). Ich kann die Wahrscheinlichkeitsbedingungen in beiden Definitionen nicht richtig unterscheiden.

Einige konkrete Beispiele mit klarem Einblick in die subtilen Punkte wären sehr hilfreich.

DurgaDatta
quelle

Antworten:

10

Das sieht für mich richtig aus. Der Unterschied zwischen BPP und PP ist , dass für die BPP die Wahrscheinlichkeit größer ist als sein muß durch eine Konstante , während für PP es sein könnte 1 / 2 + 1 / 2 n . Bei BPP-Problemen können Sie die Wahrscheinlichkeitsverstärkung mit einer kleinen Anzahl von Wiederholungen durchführen, bei allgemeinen PP-Problemen jedoch nicht.1/2 1/2+1/2n

adrianN
quelle
12

Vor's Antwort gibt die Standarddefinition. Lassen Sie mich versuchen, den Unterschied etwas intuitiver zu erklären.

Sei ein Algorithmus mit begrenzter fehlerwahrscheinlicher Polynomzeit für eine Sprache L , die mit einer Wahrscheinlichkeit von mindestens p 1 korrekt antwortetML. Seixdie Eingabe undndie Größe der Eingabe.p12+δxn

Was einen beliebigen -Algorithmus von einem B P P -Algorithmus unterscheidet, ist die positive Lücke zwischen der Wahrscheinlichkeit, x L zu akzeptieren, und der Wahrscheinlichkeit, x L zu akzeptieren . PPBPPxLxLDas Wesentliche an ist, dass die Lücke mindestens n - O beträgt ( 1 ) . Ich werde versuchen zu erklären, warum diese Unterscheidung von Bedeutung ist und es uns ermöglicht, B P P als effiziente Algorithmen zu betrachten (sogar als P angenommenBPPnO(1)BPPP) wohingegen als ineffizient angesehen wird (tatsächlich enthält P P N P ). All dies kommt von dieser Lücke.PPPPNP

Beginnen wir mit einem genaueren Blick auf PP

Es ist zu beachten, dass, wenn ein Algorithmus während seiner Ausführung höchstens Zufallsbits verwendet und die Fehlerwahrscheinlichkeit kleiner als 2 - r ( n ) ist, die Fehlerwahrscheinlichkeit tatsächlich 0 ist , es keine Auswahl von Zufallsbits geben kann, die den Algorithmus machen antworte falsch.r(n)2r(n)0

Darüber hinaus kann ein Algorithmus mit der Laufzeit nicht mehr als t ( n ) Zufallsbits verwenden. Wenn also der Fehler eines probabilistischen Algorithmus mit der Laufzeit t ( n ) im ungünstigsten Fall besser ist alst(n)t(n)t(n)

Mit einem ähnlichen Argument können wir zeigen, dass der Fall, in dem der Unterschied zwischen der Wahrscheinlichkeit, ein zu akzeptieren, und der Wahrscheinlichkeit, ein x L zu akzeptieren, zu gering ist, dem Fall ähnlich ist, in dem wir fast keinen Unterschied wie in haben P P Fall.xLxLPP

Lassen Sie uns nun in Richtung bewegen .BPP

In probabilistischen Algorithmen können wir die Wahrscheinlichkeit für eine korrekte Antwort erhöhen. Angenommen, wir möchten die Korrektheitswahrscheinlichkeit auf erhöhen, beispielsweise die Fehlerwahrscheinlichkeit ϵ = 2 - n (exponentiell kleiner Fehler).1ϵϵ=2n

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

Wie oft sollten wir ausführen , um die Fehlerwahrscheinlichkeit auf höchstens ϵ zu bringen ? Θ ( δ - 1 lg ϵ ) mal. Der Beweis wird am Ende dieser Antwort gegeben.MϵΘ(δ1lgϵ)

MΘ(δ1lnϵ)=nO(1)

δ1lgϵ=nO(1)

ϵ2nn12nO(1)

δ02nnω(1)BPP

BPP

PP


ϵ(12δ,12+δ)M Θ(δ1lgϵ)

NkMkk

xLxL

Pr{M(x) accepts}=p12+δ
Nkk

Xii0Xi

E[Xi]=Pr{Xi=1}=Pr{M(x) accepts}=p12+δ

Y=Σi=1kXiYk2

Pr{Nk(x) accepts}=Pr{Yk2}

Zμ

Pr{|Zμ|>αμ}<eα24μ

ZαμμαY<k2

E[Y]=E[Σi=1kXi]=Σi=1kE[Xi]=kpk2+kδ

Y<k2|Y(k2+kδ)|>kδ

Pr{|Ykp|>αkp}<eα24kp

ααkp=kδα=δp2δ2δ+1

Deshalb haben wir

Pr{Y<k2}Pr{|Y(k2+kδ)|>kδ}Pr{|Ykp|>αkp}<eα24kp

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

α24kpδ24δ+2k=Θ(kδ)

wir haben

Pr{Y<k2}<eΘ(kδ)

ϵ

eΘ(kδ)ϵ

oder mit anderen Worten

Θ(δ1lgϵ)k

NkkM

12

Kaveh
quelle
7

Verwenden Sie Ihre Notation:

BPP={L:M,0<c1/2xPr[χL(x)=M(x)]12+c}

PP={L:MxPr[χL(x)=M(x)]>12}

Auf den Unterschied wurde von adrianN hingewiesen, und Sie können auch einen Blick auf Wikipedia PP vs BPP werfen

Vor
quelle