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≥12+δ. Pozwolićx być wejściem i n rozmiar danych wejściowych.
Co wyróżnia arbitralność PP algorytm z BPPalgorytm to dodatnia różnica między prawdopodobieństwem akceptacjix∈L i prawdopodobieństwo przyjęcia x∉L. Najważniejsza rzeczBPP 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ćBPP być uważane za wydajne algorytmy (nawet przypuszcza się, że są równe P) natomiast PP jest uważany za nieefektywny (właściwie PP zawiera NP). Wszystko to pochodzi z tej luki.
Zacznijmy od spojrzenia na 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∈L oraz prawdopodobieństwo przyjęcia an x∉L jest zbyt mały jest podobny do przypadku, w którym nie mamy prawie żadnej różnicy jak w PP walizka.
Przejdźmy teraz do BPP.
W algorytmach probabilistycznych możemy zwiększyć prawdopodobieństwo prawidłowej odpowiedzi. Powiedzmy, że chcemy zwiększyć prawdopodobieństwo poprawności do1−ϵ na przykład prawdopodobieństwo błędu ϵ=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 ϵ? Θ(δ−1lgϵ)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ćMwięcej niż wielomianowo wiele razy. Innymi słowy,Θ(δ−1lnϵ)=nO(1)lub prościej
δ−1lgϵ=nO(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ϵ bycie 2−n lub dodatnia stała (tzn. nie zmienia się przy pomocy n) lub 12−nO(1). Możemy przejść od jednego do drugiego, pozostając w czasie wielomianowym.
Jeśli jednak δ jest za mały, powiedzmy 0, 2−n, lub nawet n−ω(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ć BPP.
Najważniejsze jest to, że w BPPmoż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 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 ϵ kiedy zaczynamy od algorytmu z przerwą (12−δ,12+δ) powinniśmy biec M Θ(δ−1lgϵ) czasy.
Pozwolić Nk być działającym algorytmem M dla krazy, a następnie odpowiedzi zgodnie z odpowiedzią większości. Dla uproszczenia załóżmy, żek jest dziwne, więc nie mamy więzi.
Rozważ przypadek, że x∈L. Walizkax∉Ljest podobny. Następnie
Pr{M(x) accepts}=p≥12+δ
Aby przeanalizować prawdopodobieństwo poprawności
Nk musimy oszacować prawdopodobieństwo, że większość
k biegi zaakceptować.
Pozwolić Xi być 1, jeśli ibieg przyjmuje i bądź 0jeśli to odrzuca. Zauważ, że każdy przebieg jest niezależny od innych, ponieważ używają niezależnych losowych bitów. A zatemXis są niezależnymi losowymi zmiennymi logicznymi, gdzie
E[Xi]=Pr{Xi=1}=Pr{M(x) accepts}=p≥12+δ
Pozwolić Y=Σki=1Xi. Musimy oszacować prawdopodobieństwo, że większość zaakceptuje, tj. Prawdopodobieństwo, żeY≥k2.
Pr{Nk(x) accepts}=Pr{Y≥k2}
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 losowejZ o oczekiwanej wartości μ, mamy
Pr{|Z−μ|>αμ}<eα24μ
co mówi, że prawdopodobieństwo, że Z jest αμ dalekie od oczekiwanej wartości μ wykładniczo zmniejsza się jako αwzrasta. Wykorzystamy to do ograniczenia prawdopodobieństwaY<k2.
Zauważ, że dzięki liniowości oczekiwań mamy
E[Y]=E[Σki=1Xi]=Σki=1E[Xi]=kp≥k2+kδ
Teraz możemy zastosować granicę Chernoffa. Chcemy górnej granicy prawdopodobieństwaY<k2. Granica Chernoffa wyznaczy górną granicę prawdopodobieństwa|Y−(k2+kδ)|>kδco jest wystarczające. Mamy
Pr{|Y−kp|>αkp}<e−α24kp
a jeśli wybieramy α takie, że αkp=kδ skończymy, więc wybieramy α=δp≤2δ2δ+1.
Dlatego mamy
Pr{Y<k2}≤Pr{|Y−(k2+kδ)|>kδ}≤Pr{|Y−kp|>αkp}<e−α24kp
a jeśli wykonasz obliczenia, zobaczysz to
α24kp≤δ24δ+2k=Θ(kδ)
mamy
Pr{Y<k2}<e−Θ(kδ)
Chcemy, aby błąd był co najwyżej ϵ, więc chcemy
e−Θ(kδ)≤ϵ
lub innymi słowy
Θ(δ−1lgϵ)≤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 Nk będzie z grubsza k razy czas działania M.
Tutaj był środek luki 12. 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.