Beweisen oder widerlegen: BPP (0,90,0,95) = BPP

8

Ich würde wirklich gern Ihre Hilfe bei der Prüfung oder Widerlegung des folgenden Anspruchs: . In der rechnerischen Komplexitätstheorie ist BPP, das für probabilistische Polynomzeit mit begrenztem Fehler steht, die Klasse von Entscheidungsproblemen, die von einer probabilistischen Turing-Maschine in Polynomzeit mit einer Fehlerwahrscheinlichkeit von höchstens 1 lösbar sindBPP(0.90,0.95)=BPP für alle Fälle. BPP=BPP(113.BPP=BPP(13,23)

Es ist nicht unmittelbar, dass eine der Mengen eine Teilmenge der anderen ist, da die Wahrscheinlichkeit für einen Fehler, wenn sie kleiner als ist, nicht kleiner als 1 sein muss0.9 und wenn es größer als2 ist13 Es muss nicht größer als0,905 sein.230.905

Ich versuche, Chernoffs Ungleichung zu nutzen, um die Behauptung zu beweisen. Ich bin mir nicht sicher, wie genau. Ich hätte wirklich gerne Ihre Hilfe. Gibt es einen allgemeinen Anspruch bezüglich dieser Beziehungen, den ich verwenden kann?

Zähler
quelle
Ich bin mir nicht sicher, was die Notation BPP (x, y) bedeutet. Wird eine Zeichenfolge, die nicht in der Sprache enthalten ist, mit einer Wahrscheinlichkeit von nicht mehr als x und eine Zeichenfolge in der Sprache mit einer Wahrscheinlichkeit von nicht mehr als y akzeptiert?
Matt Lewis
Genau, Sie sind richtig.
Zähler
4
Hinweis: Wenn Sie Versuche mit einer Zeichenfolge ausführen , die nicht in Ihrer Sprache vorliegt, wie hoch ist die Wahrscheinlichkeit, dass mehr als z. B. 9 n + c n von ihnen akzeptieren die Zeichenfolge? Wenn SienVersuche mit einer Zeichenfolgeausführen, die in der Sprachevorliegt, wiehochist die Wahrscheinlichkeit, dass weniger als0,95n-c.9 n+cnn von ihnen lehnen die Zeichenfolge ab? Was passiert mit Ihren Akzeptanz- / Ablehnungswahrscheinlichkeiten, wenn SienVersucheausführenund sagen: "Akzeptieren Sie eine Zeichenfolge, die von mehr als0,925nLäufenakzeptiert wird", alsn? .95 ncnn.925 nn
Steven Stadnicki
4
Steven Stadnicki der Hinweis ist für die zeigen , dass . Für die andere Richtung zeigen, daß B P P ( 1 / 3 , 2 / 3 ) B P P ( ε , 1 - ε ) für jeden ε . Auf die gleiche Weise können Sie zeigen, dass B P P.BPP(0.9,0.95)BPP(1/3,2/3)BPP(1/3,2/3)BPP(ϵ,1ϵ)ϵ für beliebige Konstanten 0 < α < β < 1 . BPP=BPP(α,β)0<α<β<1
Yuval Filmus

Antworten:

12

Um meinen Kommentar zu einer Antwort zu erweitern: Die multiplikative Form von Chernoffs Grenze besagt, dass wenn die Erwartung für die Summe unabhängiger zufälliger binärer Variablen μ ist , die Wahrscheinlichkeit, von 'zu weit' abzuweichen diese Erwartung lautet wie folgt : P r ( X > ( 1 + δ ) μ ) < ( e δX=i=0nXiμ.Pr(X>(1+δ)μ)<(eδ(1+δ)(1+δ))μ

σnBPP(0.90,0.95)n0.925nσn

XiiX=Xi.9nσLμ=E(X)=0.9n.90.925nX>0.925nδ=(0.9250.9)1=136(eδ(1+δ)(1+δ)).99961<29993000Pr(X>0.925n)<(29993000)0.9n

n<13nσσ.925nσL13nBPP(0.9,0.95)X<.925ncncn1323σLBPP(.9,.95)BPP(13,23)BPP

Kanonisch ist dies als Wahrscheinlichkeitsverstärkung bekannt und eine äußerst nützliche Methode für den Umgang mit Wahrscheinlichkeitsklassen. Die spezifischen Konstanten sind offensichtlich weniger wichtig als die Tatsache, dass Chernoffs Bindung es uns ermöglicht, unsere Wahrscheinlichkeiten für "falsche Ergebnisse" durch eine Exponentialfunktion der Anzahl der Versuche zu begrenzen, so dass sie mit nur einer bescheidenen Anzahl von Versuchen beliebig klein gemacht werden können.

Steven Stadnicki
quelle
2
Sie brauchen Chernoffs Bindung hier eigentlich nicht, Chebyshev reicht aus.
Yuval Filmus
@ YuvalFilmus Oh, sicher; Da OP Chernoff speziell erwähnte, dachte ich, ich würde diesen Weg gehen, und abgesehen von der unangenehmen Form der Konstante ist es meiner Meinung nach tatsächlich ein wenig einfacher, da Sie die Ergebnisse (so einfach sie auch sein mögen) nicht anhand der Varianz herausfinden müssen einer Binomialverteilung.
Steven Stadnicki