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

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 ) ] ≥ $\chi$$\mathcal{L}$
P P = { L : P r [ χ ( x ) ≠ M ( x ) ] > $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 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.

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/2^n$

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 antwortet$M$$L$. Seixdie Eingabe undndie Größe der Eingabe.$p\geq\frac{1}{2}+\delta$$x$$n$

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 . $\mathsf{PP}$$\mathsf{BPP}$$x\in L$$x\notin L$Das 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 $\mathsf{BPP}$$n^{-O(1)}$$\mathsf{BPP}$$\mathsf{P}$) wohingegen als ineffizient angesehen wird (tatsächlich enthält P P N P ). All dies kommt von dieser Lücke.$\mathsf{PP}$$\mathsf{PP}$$\mathsf{NP}$

Beginnen wir mit einem genaueren Blick auf $\mathsf{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)$$2^{-r(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 als$t(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.$x\in L$$x\notin L$$\mathsf{PP}$

Lassen Sie uns nun in Richtung bewegen .$\mathsf{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-\epsilon$$\epsilon=2^{-n}$

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$$\epsilon$$\Theta(\delta^{-1} \lg \epsilon)$

$M$$\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$

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

$\epsilon$$2^{-n}$$n$$\frac{1}{2}-n^{O(1)}$

$\delta$$0$$2^{-n}$$n^{-\omega(1)}$$\mathsf{BPP}$

$\mathsf{BPP}$

$\mathsf{PP}$

---

$\epsilon$$(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$$M$ $\Theta(\delta^{-1} \lg \epsilon)$

$N_k$$M$$k$$k$

$x \in L$$x \notin L$

$$\mathsf{Pr}\{M(x) \text{ accepts}\} = p \geq \frac{1}{2} + \delta$$ $N_k$$k$

$X_i$$i$$0$$X_i$

$$\mathbb{E}[X_i] = \mathsf{Pr}\{X_i=1\} = \mathsf{Pr}\{M(x)\text{ accepts}\} = p \geq \frac{1}{2}+\delta$$

$Y = \Sigma_{i=1}^k X_i$$Y\geq\frac{k}{2}$

$$\mathsf{Pr}\{N_k(x) \text{ accepts}\} = \mathsf{Pr}\{Y \geq \frac{k}{2}\}$$

$Z$$\mu$

$$\mathsf{Pr}\{|Z-\mu| > \alpha\mu\} < e^{\frac{\alpha^2}{4}\mu}$$

$Z$$\alpha\mu$$\mu$$\alpha$$Y < \frac{k}{2}$

$$\mathbb{E}[Y] = \mathbb{E}[\Sigma_{i=1}^k X_i] = \Sigma_{i=1}^k \mathbb{E}[X_i] = kp \geq \frac{k}{2} + k\delta$$

$Y< \frac{k}{2}$$|Y-(\frac{k}{2}+k\delta)| > k\delta$

$$Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$$

$\alpha$$\alpha kp = k\delta$$\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)}$$

$\epsilon$

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

oder mit anderen Worten

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

$N_k$$k$$M$

$\frac{1}{2}$

Verwenden Sie Ihre Notation:

$BPP =\{L : \exists$$M,$$0 < c \leq 1/2$$\forall x \; Pr[\chi_L(x) = M(x)] \geq \frac{1}{2} + c\}$

$PP =\{L : \exists$$M$$\forall x \; Pr[\chi_L(x) = M(x)] > \frac{1}{2}\}$

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