Konkretne zrozumienie różnicy między definicjami PP i BPP

9

Jestem zdezorientowany co do definicji PP i BPP . Załóżmy, że jest charakterystyczną funkcją języka . M być probabilistyczną Maszyną Turinga. Czy następujące definicje są poprawne: $\chi$ $\mathcal{L}$
$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} \}$

Jeśli definicja jest niepoprawna, spróbuj wprowadzić minimalne zmiany, aby były poprawne (tj. Nie podawaj innej równoważnej definicji, która używa maszyny liczącej lub jakiegoś zmodyfikowanego modelu). Nie mogę właściwie rozróżnić warunków prawdopodobieństwa w obu definicjach.

Bardzo pomocne byłyby konkretne przykłady z wyraźnym wglądem w subtelne punkty.

— DurgaDatta
źródło

10

Dla mnie to wygląda poprawnie. Różnica między BPP i PP polega na tym, że dla BPP prawdopodobieństwo musi być większe od o stałą , podczas gdy dla PP może wynosić . Tak więc w przypadku problemów z BPP można zwiększyć prawdopodobieństwo przy niewielkiej liczbie powtórzeń, natomiast w przypadku ogólnych problemów z PP nie można tego zrobić. $1/2$ $1/2+ 1/2^n$

— adrianN
źródło

12

Odpowiedź Vora podaje standardową definicję. Spróbujmy wyjaśnić różnicę nieco bardziej intuicyjnie.

Pozwolić $M$ być ograniczonym błędem probabilistycznym algorytmem wielomianowym dla języka $L$ który odpowiada poprawnie przynajmniej z prawdopodobieństwem $p\geq\frac{1}{2}+\delta$ . Pozwolić $x$ być wejściem i $n$ rozmiar danych wejściowych.

Co wyróżnia arbitralność $\mathsf{PP}$ algorytm z $\mathsf{BPP}$ algorytm to dodatnia różnica między prawdopodobieństwem akceptacji $x\in L$ i prawdopodobieństwo przyjęcia $x\notin L$ . Najważniejsza rzecz $\mathsf{BPP}$ jest to, że różnica jest co najmniej $n^{-O(1)}$ . Spróbuję wyjaśnić, dlaczego to rozróżnienie jest znaczące i pozwala nam rozważyć $\mathsf{BPP}$ być uważane za wydajne algorytmy (nawet przypuszcza się, że są równe $\mathsf{P}$ ) natomiast $\mathsf{PP}$ jest uważany za nieefektywny (właściwie $\mathsf{PP}$ zawiera $\mathsf{NP}$ ). Wszystko to pochodzi z tej luki.

Zacznijmy od spojrzenia na $\mathsf{PP}$ bardziej ostrożnie.

Zauważ, że jeśli algorytm używa co najwyżej $r(n)$ losowe bity podczas jego wykonywania, a prawdopodobieństwo błędu jest mniejsze niż $2^{-r(n)}$ wtedy prawdopodobieństwo błędu jest w rzeczywistości $0$ , nie można wybrać losowych bitów, które spowodowałyby, że algorytm odpowiedziałby niepoprawnie.

Ponadto algorytm z czasem działania $t(n)$ nie można użyć więcej niż $t(n)$ losowe bity, więc jeśli algorytm probabilistyczny popełni błąd błędu w najgorszym przypadku $t(n)$ jest lepszy niż

Podobnym argumentem możemy wykazać, że przypadek, w którym różnica między prawdopodobieństwem przyjęcia an $x\in L$ oraz prawdopodobieństwo przyjęcia an $x\notin L$ jest zbyt mały jest podobny do przypadku, w którym nie mamy prawie żadnej różnicy jak w $\mathsf{PP}$ walizka.

Przejdźmy teraz do $\mathsf{BPP}$ .

W algorytmach probabilistycznych możemy zwiększyć prawdopodobieństwo prawidłowej odpowiedzi. Powiedzmy, że chcemy zwiększyć prawdopodobieństwo poprawności do $1-\epsilon$ na przykład prawdopodobieństwo błędu $\epsilon=2^{-n}$ (wykładniczo mały błąd).

Pomysł jest prosty: biegnij $M$ kilka razy i weź odpowiedź większości.

Ile razy powinniśmy biegać $M$ aby uzyskać maksymalne prawdopodobieństwo błędu $\epsilon$ ? $\Theta(\delta^{-1} \lg \epsilon)$ czasy. Dowód znajduje się na dole tej odpowiedzi.

Teraz weźmy pod uwagę, że omawiane algorytmy muszą być czasem wielomianowym. Oznacza to, że nie możemy biegać $M$ więcej niż wielomianowo wiele razy. Innymi słowy, $\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$ lub prościej

δ^{- 1} \lg ϵ = n^{O (1)}

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

Zależność ta dzieli algorytmy probabilistyczne na ograniczone błędy na klasy w zależności od ich prawdopodobieństwa błędu. Nie ma różnicy między prawdopodobieństwem błędu $\epsilon$ bycie $2^{-n}$ lub dodatnia stała (tzn. nie zmienia się przy pomocy $n$ ) lub $\frac{1}{2}-n^{O(1)}$ . Możemy przejść od jednego do drugiego, pozostając w czasie wielomianowym.

Jeśli jednak $\delta$ jest za mały, powiedzmy $0$ , $2^{-n}$ , lub nawet $n^{-\omega(1)}$ wtedy nie mamy sposobu na zwiększenie prawdopodobieństwa poprawności i zmniejszenie prawdopodobieństwa błędu w stopniu wystarczającym, aby się do niego dostać $\mathsf{BPP}$ .

Najważniejsze jest to, że w $\mathsf{BPP}$ możemy efektywnie zmniejszyć prawdopodobieństwo błędu wykładniczo, więc jesteśmy prawie pewni odpowiedzi i właśnie dlatego uważamy tę klasę algorytmów za wydajne. Prawdopodobieństwo błędu można zmniejszyć do tego stopnia, że awaria sprzętu jest bardziej prawdopodobna lub nawet meteoryt spadający na komputer jest bardziej prawdopodobny niż popełnianie błędu przez algorytm probabilistyczny.

To nie jest prawda $\mathsf{PP}$ , nie znamy żadnego sposobu na zmniejszenie prawdopodobieństwa błędu i pozostajemy prawie tak, jakbyśmy odpowiadali rzucając monetą w celu uzyskania odpowiedzi (nie jesteśmy do końca, prawdopodobieństwo nie jest w połowie, ale jest bardzo blisko do tej sytuacji).

W tej sekcji przedstawiono dowód na prawdopodobieństwo wystąpienia błędu $\epsilon$ kiedy zaczynamy od algorytmu z przerwą $(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$ powinniśmy biec $M$ $\Theta(\delta^{-1} \lg \epsilon)$ czasy.

Pozwolić $N_k$ być działającym algorytmem $M$ dla $k$ razy, a następnie odpowiedzi zgodnie z odpowiedzią większości. Dla uproszczenia załóżmy, że $k$ jest dziwne, więc nie mamy więzi.

Rozważ przypadek, że $x \in L$ . Walizka $x \notin L$ jest podobny. Następnie

P r {M (x) accepts} = p \geq \frac{1}{2} + δ

$\mathsf{Pr}\{M(x) \text{ accepts}\} = p \geq \frac{1}{2} + \delta$ Aby przeanalizować prawdopodobieństwo poprawności

N_{k}

$N_k$ musimy oszacować prawdopodobieństwo, że większość

k

$k$ biegi zaakceptować.

Pozwolić $X_i$ być 1, jeśli $i$ bieg przyjmuje i bądź $0$ jeśli to odrzuca. Zauważ, że każdy przebieg jest niezależny od innych, ponieważ używają niezależnych losowych bitów. A zatem $X_i$ s są niezależnymi losowymi zmiennymi logicznymi, gdzie

E [X_{i}] = P r {X_{i} = 1} = P r {M (x) accepts} = p \geq \frac{1}{2} + δ

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

Pozwolić $Y = \Sigma_{i=1}^k X_i$ . Musimy oszacować prawdopodobieństwo, że większość zaakceptuje, tj. Prawdopodobieństwo, że $Y\geq\frac{k}{2}$ .

P r {N_{k} (x) accepts} = P r {Y \geq \frac{k}{2}}

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

Jak to zrobić? Możemy użyć granicy Chernoffa, która mówi nam o koncentracji prawdopodobieństwa w pobliżu oczekiwanej wartości. Dla dowolnej zmiennej losowej $Z$ o oczekiwanej wartości $\mu$ , mamy

P r {| Z - μ | > α μ} < e^{\frac{α^{2}}{4} μ}

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

co mówi, że prawdopodobieństwo, że $Z$ jest $\alpha\mu$ dalekie od oczekiwanej wartości $\mu$ wykładniczo zmniejsza się jako $\alpha$ wzrasta. Wykorzystamy to do ograniczenia prawdopodobieństwa $Y < \frac{k}{2}$ .

Zauważ, że dzięki liniowości oczekiwań mamy

E [Y] = E [Σ_{i = 1}^{k} X_{i}] = Σ_{i = 1}^{k} E [X_{i}] = k p \geq \frac{k}{2} + k δ

$\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$

Teraz możemy zastosować granicę Chernoffa. Chcemy górnej granicy prawdopodobieństwa $Y< \frac{k}{2}$ . Granica Chernoffa wyznaczy górną granicę prawdopodobieństwa $|Y-(\frac{k}{2}+k\delta)| > k\delta$ co jest wystarczające. Mamy

P r {| Y - k p | > α k p} < e^{- \frac{α^{2}}{4} k p}

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

a jeśli wybieramy $\alpha$ takie, że $\alpha kp = k\delta$ skończymy, więc wybieramy $\alpha = \frac{\delta}{p} \leq \frac{2\delta}{2\delta+1}$ .

Dlatego mamy

P r {Y < \frac{k}{2}} \leq P r {| Y - (\frac{k}{2} + k δ) | > k δ} \leq P r {| Y - k p | > α k p} < e^{- \frac{α^{2}}{4} k p}

$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}$

a jeśli wykonasz obliczenia, zobaczysz to

\frac{α^{2}}{4} k p \leq \frac{δ^{2}}{4 δ + 2} k = Θ (k δ)

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

mamy

P r {Y < \frac{k}{2}} < e^{- Θ (k δ)}

$Pr\{Y < \frac{k}{2} \} < e^{-\Theta(k\delta)}$

Chcemy, aby błąd był co najwyżej $\epsilon$ , więc chcemy

e^{- Θ (k δ)} \leq ϵ

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

lub innymi słowy

Θ (δ^{- 1} \lg ϵ) \leq k

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

Jednym z istotnych punktów jest to, że w procesie wykorzystamy o wiele więcej losowych bitów, a także wydłuży się czas działania, tj. Najgorszy możliwy czas działania $N_k$ będzie z grubsza $k$ razy czas działania $M$ .

Tutaj był środek luki $\frac{1}{2}$ . Ale generalnie nie musi tak być. Możemy zastosować podobną metodę dla innych wartości, przyjmując inne ułamki zamiast większości do zaakceptowania.

— Kaveh
źródło

7

Korzystanie z notacji:

$BPP =\{L : \exists$ probabilistyczna maszyna Turinga w czasie wielomianowym $M,$ i kosztowny $0 < c \leq 1/2$ takie, że $\forall x \; Pr[\chi_L(x) = M(x)] \geq \frac{1}{2} + c\}$

$PP =\{L : \exists$ probabilistyczna maszyna Turinga w czasie wielomianowym $M$ takie, że $\forall x \; Pr[\chi_L(x) = M(x)] > \frac{1}{2}\}$

Różnica została wskazana przez adrianN, a także możesz spojrzeć na Wikipedię PP vs BPP

— Vor
źródło