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

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 lösbar sind $BPP(0.90,0.95)=BPP$ für alle Fälle. $\frac{1}{3}$ . $BPP=BPP(\frac{1}{3},\frac{2}{3})$

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 $0.9$ und wenn es größer als $\frac{1}{3}$ Es muss nicht größer als. $\frac{2}{3}$ $0.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?

complexity-theory time-complexity probabilistic-algorithms 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

Hinweis: Wenn Sie

Versuche mit einer Zeichenfolge ausführen , die nicht in Ihrer Sprache vorliegt, wie

ist die Wahrscheinlichkeit, dass mehr als z. B.

n

$n$

von ihnen akzeptieren die Zeichenfolge? Wenn Sie

Versuche mit einer Zeichenfolgeausführen, die in der Sprache

, wie

ist die Wahrscheinlichkeit, dass weniger als

.9 n + c \sqrt{n}

$.9\ n+c\sqrt{n}$

n

$n$

von ihnen lehnen die Zeichenfolge ab? Was passiert mit Ihren Akzeptanz- / Ablehnungswahrscheinlichkeiten, wenn Sie

Versucheausführenund sagen: "Akzeptieren Sie eine Zeichenfolge, die von mehr als

Läufenakzeptiert wird", als

.95 n - c \sqrt{n}

$.95\ n-c\sqrt{n}$

n

$n$

.925 n

$.925\ n$

n \to \infty

$n\to\infty$

Steven Stadnicki

Steven Stadnicki der Hinweis ist für die zeigen , dass

. Für die andere Richtung zeigen, daß

für jeden

. Auf die gleiche Weise können Sie zeigen, dass

B P P (0.9, 0.95) \subseteq B P P (1 / 3, 2 / 3)

$BPP(0.9,0.95) \subseteq BPP(1/3,2/3)$

B P P (1 / 3, 2 / 3) \subseteq B P P (ϵ, 1 - ϵ)

$BPP(1/3,2/3) \subseteq BPP(\epsilon,1-\epsilon)$

ϵ

$\epsilon$

für beliebige Konstanten

B P P = B P P (α, β)

$BPP = BPP(\alpha,\beta)$

0 < α < β < 1

$0<\alpha<\beta<1$

Yuval Filmus

Antworten:

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 , die Wahrscheinlichkeit, von 'zu weit' abzuweichen diese Erwartung lautet wie : $X=\sum_{i=0}^n X_i$ $\mu$ . $Pr(X\gt (1+\delta)\mu) \lt \left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right)^\mu$

$\sigma$ $n$ $BPP(0.90, 0.95)$ $n$ $0.925n$ $\sigma$ $n$

$X_i$ $i$ $X=\sum X_i$ $.9$ $n$ $\sigma\notin L$ $\mu = E(X) = 0.9n$ $.9$ $0.925n$ $X\gt 0.925n$ $\delta = \left(\frac{0.925}{0.9}\right)-1 =\frac{1}{36}$ $\left(\dfrac{e^\delta}{(1+\delta)^{(1+\delta)}}\right) \approx.99961\lt \frac{2999}{3000}$ $Pr(X\gt 0.925n)\lt\left(\frac{2999}{3000}\right)^{0.9n}$

$n$ $\lt\frac{1}{3}$ $n$ $\sigma$ $\sigma$ $.925n$ $\sigma\notin L$ $\frac{1}{3}$ $n$ $BPP(0.9, 0.95)$ $X\lt.925n$ $c^n$ $c$ $n$ $\frac{1}{3}$ $\frac{2}{3}$ $\sigma\in L$ $BPP(.9, .95)\subseteq BPP(\frac13, \frac23) \equiv 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

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