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:χL
BPP={L:Pr[χ(x)M(x)]12+ϵxL, ϵ>0}
PP={L:Pr[χ(x)M(x)]>12}

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

Odpowiedzi:

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

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 p12+δ. 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 akceptacjixL i prawdopodobieństwo przyjęcia xL. Najważniejsza rzeczBPP jest to, że różnica jest co najmniej nO(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ż 2r(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 xL oraz prawdopodobieństwo przyjęcia an xL 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 ϵ=2n (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 2n lub dodatnia stała (tzn. nie zmienia się przy pomocy n) lub 12nO(1). Możemy przejść od jednego do drugiego, pozostając w czasie wielomianowym.

Jeśli jednak δ jest za mały, powiedzmy 0, 2n, 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 xL. WalizkaxLjest podobny. Następnie

Pr{M(x) accepts}=p12+δ
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}=p12+δ

Pozwolić Y=Σi=1kXi. Musimy oszacować prawdopodobieństwo, że większość zaakceptuje, tj. Prawdopodobieństwo, żeYk2.

Pr{Nk(x) accepts}=Pr{Yk2}

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[Σi=1kXi]=Σi=1kE[Xi]=kpk2+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{|Ykp|>αkp}<eα24kp

a jeśli wybieramy α takie, że αkp=kδ skończymy, więc wybieramy α=δp2δ2δ+1.

Dlatego mamy

Pr{Y<k2}Pr{|Y(k2+kδ)|>kδ}Pr{|Ykp|>α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.

Kaveh
źródło
7

Korzystanie z notacji:

BPP={L: probabilistyczna maszyna Turinga w czasie wielomianowym M, i kosztowny 0<c1/2 takie, że xPr[χL(x)=M(x)]12+c}

PP={L: probabilistyczna maszyna Turinga w czasie wielomianowym M takie, że xPr[χL(x)=M(x)]>12}

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

Vor
źródło