Złożoność obliczeniowa/Wykład 10: Algorytmy probabilistyczne

Algorytmy probabilistyczne

probabilistyczne klasy złożoności,
rozpoznawanie liczb pierwszych.

Probabilistyczne klasy złożoności

W tym module podejmujemy próbę teoretycznej analizy obliczeń, w których pojawia się losowość. Rozpoczynamy od wprowadzenia losowości do naszego modelu obliczeń.

Załóżmy, że $M$ jest zwykłą niedeterministyczną maszyną Turinga. Przypomnijmy, że $M$ ma podczas każdego kroku obliczeń możliwość wyboru wielu ścieżek obliczeń. W pojęciu akceptacji słowa bierzemy pod uwagę zachowanie $M$ na wszystkich jej ścieżkach. Taka konstrukcja sprawia, że niedeterministyczny model obliczeń jest przydatny z czysto teoretycznego punktu widzenia, albowiem w praktyce takich maszyn zbudować nie umiemy.

Prosty pomysł, który pozwala zaadaptować ideę wielu możliwości, polega właśnie na losowaniu. Bez straty ogólności przyjmijmy, że na każdym kroku maszyna $M$ wybiera spośród dwóch możliwości wyboru ścieżki. Wyobraźmy sobie, że maszyna $M$ może rzucić monetą i na podstawie wyniku wybrać jedną z dwóch ścieżek. Prawidłową realizację takiego losowania i problemy jakie się z tym wiążą omówimy w dalszej części. W tym momencie jest dla nas najważniejsze, że jest to podejście jak najbardziej praktyczne.

Opisaną powyżej maszynę Turinga $M$ nazywamy probabilistyczną. Maszyna probabilistyczna akceptuje słowo wejściowe $x$ wtedy, gdy dojdzie do stanu akceptującego. Ponieważ na każdym kroku dokonuje ona losowania, to akceptacja odbywa się z pewnym prawdopodobieństwem. Podobnie jest z odrzucaniem słowa wejściowego:

Definicja 1.1.

Dla probabilistycznej maszyny Turinga $M$ i słowa wejściowego $x$ definiujemy $P_{M} (x)$ jako prawdopodobieństwo, że maszyna $M$ zaakceptuje słowo $x$ .

Powyższe prawdopodobieństwo jest obliczane w sposób naturalny, na podstawie analizy możliwych ścieżek obliczeń.

Zauważmy, że maszyna deterministyczna jest szczególnym przypadkiem maszyny probabilistycznej -- to po prostu maszyna probabilistyczna, która nie wykonuje rzutów monetą w żadnym kroku (lub nie mają one wpływu na wynik obliczeń). Dla konkretnej maszyny deterministycznej $M$ , jej języka $L = L (M)$ i słowa wejściowego $x$ zachodzi zatem:

$x \in L \Rightarrow P_{M} (x) = 1$
$x \notin L \Rightarrow P_{M} (x) = 0$

Naszym obiektem zainteresowania jest powiązanie prawdopodobieństwa akceptacji słowa z jego przynależnością do konkretnego języka $L$ . W ten sposób będziemy mogli używać maszyny probabilistycznej do akceptowania $L$ podobnie jak maszyny deterministycznej. Nie będziemy wymagać tak ścisłej zależności pomiędzy przynależnością do języka a prawdopodobieństwem akceptacji jak podana powyżej. Dzięki rozluźnieniu warunków okaże się, że łatwiej znaleźć maszynę probabilistyczną dla pewnych języków. Jednocześnie jednak rezygnując z determinizmu, badanie przynależności słowa do języka będzie wymagać szczególnej uwagi. Będzie bowiem dochodzić do sytuacji, że maszyna probabilistyczna będzie się mylić.

Błąd maszyny probabilistycznej $M$ może być dwojakiego rodzaju. Ustalmy $L$ . Jeśli $x \in L$ to $M$ akceptuje $x$ z prawdopodobieństwem $P_{M} (x)$ . Jeśli nie jest ono równe 1, to może się okazać, że $M$ odrzuci $x$ . Mówimy wtedy o fałszywej odpowiedzi negatywnej. Maszyna odrzuca poprawne słowo z języka $L$ !

W drugim przypadku $x \notin L$ i $M$ akceptuje $x$ z prawdopodobieństwem $P_{M} (x)$ . Jeśli nie jest ono równe 0, to może się okazać, że $M$ zaakceptuje $x$ . Mówimy wtedy o fałszywej odpowiedzi pozytywnej. Maszyna akceptuje słowo spoza języka $L$ !

Na pierwszy rzut oka taka maszyna może wydawać się bezużyteczna. Jeśli jednak jej omylność uda nam się okiełznać, to może to dać bardzo interesujące efekty praktyczne.

Za sztandarowy przykład służy problem decyzyjny rozpoznawania liczb pierwszych. Mimo, iż od niedawna znany jest algorytm deterministyczny, to w praktyce używa się właśnie (znacznie starszych) metod probabilistycznych, gdyż są zdecydowanie szybsze, a prawdopodobieństwo błędu jest z praktycznego punktu widzenia zaniedbywalne. W literaturze można znaleźć w tym miejscu często odwołanie do faktu, że każdy algorytm deterministyczny w praktyce działa na komputerze, w którym może wystąpić błąd natury fizycznej lub inne zdarzenie losowe, stąd w praktyce prawdziwego determinizmu nie ma. Rozpoznawaniem pierwszości zajmiemy się precyzyjnie w następnym rozdziale.

Kolejnym krokiem naszej analizy jest wprowadzenie probabilistycznych klas złożoności. Za podstawową z nich można uznać:

Definicja 1.2.[Klasa $RP$ ]]

Klasa $RP$ (ang. Randomized Polynomial) to klasa tych języków $L$ , dla których istnieje maszyna probabilistyczna $M$ , działająca w czasie wielomianowym, o następującej własności:

$x \in L \Rightarrow P_{M} (x) \geq \frac{1}{2}$ ,
$x \notin L \Rightarrow P_{M} (x) = 0$ .

Innymi słowy, maszyna nie daje fałszywych odpowiedzi pozytywnych, a prawdopodobieństwo fałszywej odpowiedzi negatywnej wynosi co najwyżej $\frac{1}{2}$ . Co dla Nas oznacza to w praktyce?

Wyobraźmy sobie, że mamy język $L$ z klasy $RP$ i maszynę $M$ dla niego. Uruchamiamy $M$ na $x$ . Maszyna działa w czasie wielomianowym. Gdy dostajemy odpowiedź ""TAK"" to jest super, bo nie daje ona fałszywych odpowiedzi pozytywnych, więc słowo na pewno należy do $L$ .

Gdy otrzymujemy odpowiedź ""NIE"" to mamy kłopot. Maszyna mogła bowiem dać fałszywą odpowiedź negatywną z prawdopodobieństwem ograniczonym z góry przez $\frac{1}{2}$ . W tym momencie wykonujemy jednak genialny w swojej prostocie manewr - uruchamiamy $M$ jeszcze raz!

W idealnej sytuacji obliczenie wykonane za drugim razem jest kompletnie niezależne od pierwszego. Gdy otrzymamy odpowiedź ""TAK"" to po kłopocie. Gdy ponownie ""NIE"" to próba nie poszła na marne, gdyż prawdopodobieństwo błędu jest teraz ograniczone z góry przez $\frac{1}{4}$ .

W tym miejscu dokładnie widać dlaczego odwoływaliśmy się wcześniej do zastosowań praktycznych. Jeśli bowiem powtórzymy próbę 100 razy, to prawdopodobieństwo błędu nie przekracza $\frac{1}{2^{100}}$ co jest według prostego szacunku równie prawdopodobne, co trafienie komputera przez spadający meteoryt podczas obliczeń. W tym momencie możemy przerwać powtarzanie i uznać, że odpowiedź brzmi ""NIE"". Aby trochę ostudzić zapał zwróćmy uwagę, że niezależność kolejnych obliczeń i wiążąca się z tym niezależność losowych wyborów jest istotnym wyzwaniem praktycznym, do czego jeszcze wrócimy.

Algorytmy o powyższej własności są też nazywane algorytmami Monte Carlo od słynnego kasyna w Monaco, którego odwiedzanie wiąże się z procesem losowania i powtarzania kolejnych prób aż do upragnionego skutku w postaci wygranej. Algorytmy Monte Carlo to określenie na szerszą klasę metod, w których określone jest prawdopodobieństwo błędu.

Poniższy fakt jest dosyć zaskakujący. Okazuje się, że stała $\frac{1}{2}$ w definicji klasy $RP$ nie ma żadnego znaczenia i wystarczy nam, żeby była dodatnia:

Ćwiczenie 1.3.

Pokaż, że stała $\frac{1}{2}$ w definicji klasy $RP$ może zostać zamieniona na dowolną stałą z przedziału $(0, 1]$ lub nawet zależeć od $x$ poprzez $\frac{1}{p (| x |)}$ , gdzie $p$ jest wielomianem.

Wskazówka

Rozwiązanie

Załóżmy, że dla $x \in L$ mamy $P_{M} (x) \geq α$ . Załóżmy $α < \frac{1}{2}$ . Jak uzyskać prawdopodobieństwo przynajmniej $\frac{1}{2}$ ? Konstruujemy maszynę $M^{'}$ , która działa poprzez uruchomienie maszyny $M$ kolejno $k$ razy. Jeśli za którymkolwiek razem dostaniemy odpowiedź ""TAK"" to kończymy obliczenia dając odpowiedź ""TAK"", w przeciwnym wypadku dajemy odpowiedź ""NIE"".

Jak zmieniły się prawdopodobieństwa? Jeśli $x \notin L$ to $P_{M^{'}} (x) = 0$ , gdyż w tym przypadku maszyna $M$ nigdy nie popełnia błędu i w każdym z $k$ powtórzeń da odpowiedź ""NIE"".

Jeśli $x \in L$ , to aby $M^{'}$ dała odpowiedź ""NIE"", maszyna $M$ musi $k$ razy dać odpowiedź ""NIE"". Ponieważ są to obliczenia niezależne, stąd $P_{M^{'}} (x) \geq 1 - (1 - α)^{k}$ .

Jeśli chcemy, aby $1 - (1 - α)^{k} \geq \frac{1}{2}$ , to $k \geq ⌈ - 1 /$ log $(1 - α) ⌉$ . Jeśli zatem $α$ jest dowolną stałą z przedziału $(0, \frac{1}{2})$ to $k$ również jest stałą i mamy gotowe rozwiązanie polegające na stałej ilości powtórzeń obliczeń.

Jeśli natomiast jeszcze bardziej rozluźnimy warunki dopuszczając, aby $P_{M} (x) \geq 1 / p (| x |)$ to $k$ będzie funkcją $| x |$ , więc musimysprawdzić, czy nie wymagamy zbyt dużej liczby powtórzeń - maszyna $M^{'}$ musi bowiem działać w czasie wielomianowym od $| x |$ . Okazuje się jednak, że gdy $p$ jest wielomianem, to potrzebne $k$ jest funkcją wielomianową od $| x |$ , dokładnie tak jak tego potrzebujemy (poniższe własności wynikają z asymptotycznego zachowania się wyrażenia):

k \approx - \frac{1}{log (1 - \frac{1}{p (| x |)})} \approx p (| x |)

Zaznaczyliśmy już wcześniej, że maszyna probabilistyczna stanowi uogólnienie maszyny deterministycznej, stąd $P \subseteq RP$ . Jak zwykle ani o tym, ani o poniższym zawieraniu nie wiemy czy jest ścisłe:

Ćwiczenie 1.4.

Pokaż, że $RP \subseteq NP$ .

Wskazówka

Rozwiązanie

Gdy język $L$ należy do $RP$ , to istnieje dla niego maszyna probabilistyczna $M$ . Definiując maszynę probabilistyczną powiedzieliśmy, że jest to maszyna niedeterministyczna, która potrafi losować i na tej podstawie wybierać ścieżkę, którą kontynuuje obliczenia. Gdy zapomnimy na chwilę o powyższym losowaniu i wybieraniu, to zauważymy, że drzewo obliczeń maszyny probabilistycznej to drzewo obliczeń maszyny niedeterministycznej. Traktujemy od tej pory $M$ jako maszynę niedeterministyczną. Pokażemy, że $L = L (M)$ .

Jeśli $x \in L$ , to z definicji $RP$ mamy $P_{M} (x) \geq \frac{1}{2}$ , czyli prawdopodobieństwo akceptacji jest niezerowe. Stąd wiemy, że istnieje przynajmniej jedna ścieżka obliczeń w $M$ , na której $x$ jest akceptowane, stąd $x \in L (M)$ .

Jeśli $x \notin L$ , to $P_{M} (x) = 0$ , czyli prawdopodobieństwo akceptacji jest zerowe. Stąd wiemy, że na żadnej ścieżce obliczeń w $M$ nie da się dojść do stanu akceptującego, stąd $x \notin L (M)$ .

Maszyny z klasy $RP$ w swojej definicji posiadają pewną asymetrię. Określa się również ich błąd jako jednostronny (ang. one-sided error). Gdy rozważymy klasę komplementarną $coRP$ , to otrzymamy symetryczne własności maszyn. Ich błąd w dalszym ciągu jest jednostronny, lecz tym razem maszyny nie dają fałszywych odpowiedzi negatywnych, czyli gdy maszyna z klasy $coRP$ daje odpowiedź ""NIE"" to słowo na pewno do języka nie należy. Natomiast prawdopodobieństwo fałszywej odpowiedzi pozytywnej jest ograniczone przez $\frac{1}{2}$ . Wszystkie własności są dualne, w szczególności $coRP \subseteq coNP$ .

Definicja 1.5. [Klasa $coRP$ ]

Klasa $coRP$ to klasa tych języków $L$ , dla których istnieje maszyna probabilistyczna $M$ , działająca w czasie wielomianowym, o następującej własności:

$x \in L \Rightarrow P_{M} (x) = 1$ .
$x \notin L \Rightarrow P_{M} (x) \leq \frac{1}{2}$ ,

Klasa $ZPP$

Odpowiedź na pytanie, czy $RP = coRP$ nie jest znana. Bez tej odpowiedzi możemy jednak rozważyć klasę $RP \cap coRP$ . Problemy, które znajdują się w tej klasie posiadają dwa algorytmy Monte Carlo z błędami jednostronnymi, ale różnymi. Możemy zatem uruchomić je jednocześnie. Działamy tak długo, aż otrzymamy od przynajmniej jednego z nich odpowiedź, która jest z całą pewnością dobra (może to być zarówno ""TAK"" jak i ""NIE""), a następnie zwracamy ją jako wynik.

Taka konstrukcja powoduje, że nasz algorytm zawsze da odpowiedź poprawną, jednak jego czas działania jest dla nas nieokreślony. Możemy jedynie policzyć czas oczekiwany, który okazuje się być wielomianowy. Prawdopodobieństwo, że trzeba będzie dokonać $k$ prób obu algorytmów wynosi $2^{- k}$ , czyli maleje wykładniczo.

Algorytmy o powyższej własności również doczekały się swojej nazwy i są określane jako algorytmy Las Vegas. Dla takich algorytmów wiemy, że zawsze dają poprawną odpowiedź, jednak ich czas działania określamy z pewnym prawdopodobieństwem. Nawiązuje to do słynnego miasta, w którym nigdy nie przegrywamy, jednak nie wiadomo jak długo będziemy grać.

Definicja 1.6. [Klasa $ZPP$ ]

Klasa $ZPP$ (ang. Zero-error Probabilistic Polynomial) to klasa tych języków $L$ , dla których istnieje maszyna probabilistyczna $M$ działająca w oczekiwanym czasie wielomianowym, która akceptuje $L$ nie popełniając błędu.

Nietrudno pokazać, że $ZPP = RP \cap coRP$ . W niektórych zastosowaniach znacznie cenniejsza od czasu działania jest absolutna poprawność odpowiedzi, stąd algorytmy Las Vegas również znajdują swoje zastosowanie w praktyce.

Klasa $PP$

Rozważając kolejne klasy zrezygnujemy z jednostronności błędu, która występowała w $RP$ .

Definicja 1.7. [Klasa $PP$ ]

Klasa $PP$ (ang. Probabilistic Polynomial) to klasa tych języków $L$ , dla których istnieje maszyna probabilistyczna $M$ działająca w czasie wielomianowym o następującej własności:

$x \in L \Rightarrow P_{M} (x) > \frac{1}{2}$ ,
$x \notin L \Rightarrow P_{M} (x) \leq \frac{1}{2}$ .

Ponieważ występujące w definicji prawdopodobieństwo błędu może być dowolnie bliskie $\frac{1}{2}$ , to skutecznie utrudnia to wydedukowanie prawidłowej odpowiedzi na podstawie wyniku losowych obliczeń maszyny. Może się bowiem zdarzyć, że prawdopodobieństwo różni się od $\frac{1}{2}$ tylko o $\frac{1}{2^{p (n)}}$ , gdzie $p$ jest wielomianem. Dzieje się tak wtedy, gdy przewaga liczby ścieżek akceptujących nad odrzucającymi poprawne słowo jest stała.

Jeśli chcielibyśmy powtarzać kolejne wywołania maszyny, tak jak to się zrobiliśmy w przypadku klasy $RP$ to w sytuacji odchylenia $\frac{1}{2^{p (n)}}$ będziemy musieli wykonać wykładniczą liczbę powtórzeń, aby uzyskać prawdopodobieństwo błędu ograniczone przez $\frac{1}{4}$ . Prześledzimy to dokładnie w następnym rozdziale, w którym rozważana klasa będzie mieć prawdopodobieństwo błędu oddalone od $\frac{1}{2}$ o stałą.

Taka sytuacja sprawia, że odpowiedź maszyny z klasy $PP$ przypominać może rzut monetą o bardzo niewielkim odchyleniu od symetrii. Zwróćmy uwagę, że w sytuacji granicznej, gdy oba prawdopodobieństwa występujące w definicji są dokładnie równe $\frac{1}{2}$ , to maszyna nie różni się niczym od pojedynczego rzutu monetą, który nie niesie żadnej informacji o języku $L$ . To wszystko sprawia, że maszyny z klasy $PP$ nie są atrakcyjne w praktycznych obliczeniach.

Dzięki rozluźnieniu warunków możemy jednak udowodnić więcej o samej klasie:

Ćwiczenie 1.8.

Udowodnij, że $NP \subseteq PP$

Wskazówka

Skonstruuj maszynę odpowiednią dla klasy $PP$ na podstawie maszyny dla klasy $NP$ .

Rozwiązanie

Weźmy dowolny język $L$ z $NP$ i maszynę $M$ , która go akceptuje. Skonstruujemy maszynę probabilistyczną $M^{'}$ z klasy $PP$ , która akceptuje $L$ . Dodajemy nowy stan początkowy, z którego w sposób losowy wychodzimy albo do stanu akceptującego, albo do normalnego obliczenia maszyny $M$ . W każdym z niedeterministycznych wyborów $M$ rzucamy monetą dokonując wyboru ścieżki (rysunek Konstrukcja maszyny).

Jeśli $x \in L$ , to można łatwo sprawdzić, że $P_{M^{'}} (x) > \frac{1}{2}$ . Jest tak dlatego, gdyż $\frac{1}{2}$ pochodzi od nowo dodanej ścieżki, a maszyna $M$ przynajmniej na jednej ze swoich ścieżek również zaakceptuje $x$ .

Jeśli natomiast $x \notin L$ , to jedyny sposób akceptacji jest poprzez nowo dodaną ścieżkę akceptującą, gdyż maszyna $M$ na żadnej ścieżce nie akceptuje $x$ . Stąd $P_{M^{'}} (x) = \frac{1}{2}$ .

Rozważmy następujący problem:

Definicja 1.9.

Problem MAJSAT:
Wejście: formuła logiczna $ϕ$ jak dla SAT o $n$ zmiennych
Wyjście: czy większość spośród możliwych $2^{n}$ wartościowań spełnia $ϕ$ ?

Ćwiczenie 1.10

Pokaż, że MAJSAT należy do $PP$ .

Wskazówka

Rozwiązanie

Konstruujemy maszynę probabilistyczną $M$ , która w swoim drzewie obliczeń rozważa wszystkie możliwości wartościowań i dochodzi do każdego z jednakowym prawdopodobieństwem $\frac{1}{2^{n}}$ . Rozważmy formułę $ϕ$ (kodowaną przez słowo $x$ ) z $n$ zmiennymi. Oznaczmy liczbę wartościowań spełniających $ϕ$ poprzez $s$ . Gdy $x \in L$ , to $s > 2^{n - 1}$ , zatem $P_{M} (x) = \frac{s}{2^{n}} > \frac{1}{2}$ . Jeśli natomiast $x \notin L$ , to $s \leq 2^{n - 1}$ , zatem $P_{M} (x) = \frac{s}{2^{n}} \leq \frac{1}{2}$ .

MAJSAT jest nawet problemem zupełnym dla klasy $PP$ . Nie wiemy o nim natomiast czy należy do $NP$ . To pokazuje, jak silna jest klasa $PP$ -- maszyn akceptujących większością.

Klasa $BPP$

W tym rozdziale prezentujemy najszerszą z klas, która odpowiada praktycznym obliczeniom losowym:.

Definicja 1.11 [Klasa $BPP$ ]

Klasa $BPP$ (ang. Bounded-error Probabilistic Polynomial) to klasa tych języków $L$ , dla których istnieje maszyna probabilistyczna $M$ działająca w czasie wielomianowym o następującej własności:

$x \in L \Rightarrow P_{M} (x) \geq \frac{3}{4}$ ,
$x \notin L \Rightarrow P_{M} (x) \leq \frac{1}{4}$ .

Niecodziennym faktem jest, że nie wiadomo nic na temat zawierania się pomiędzy klasami $NP$ i $BPP$ w żadną stronę. Klasa $BPP$ zawiera w sobie natomiast $RP$ oraz $coRP$ , co wynika wprost z definicji.

Patrząc na definicję klasy $BPP$ możemy w sposób równoważny powiedzieć, że prawdopodobieństwo popełnienia błędu przez maszynę z tej klasy jest ograniczone dla obu przypadków przez $\frac{1}{4}$ . Podobnie jak dla klasy $RP$ ta stała może zostać wybrana dowolnie z przedziału $(0, \frac{1}{2})$ , lecz jest to fakt trudniejszy:

Twierdzenie 1.12

Niech $α \in (0, \frac{1}{2})$ . Dla dowolnej maszyny probabilistycznej $M$ działającej w czasie wielomianowym, o prawdopodobieństwie błędu ograniczonym przez $\frac{1}{2} - α$ , istnieje równoważna wielomianowa maszyna probabilistyczna $M^{'}$ o prawdopodobieństwie błędu ograniczonym przez $\frac{1}{2^{p (n)}}$ , gdzie $p$ jest wielomianem.

Dowód

Mamy do dyspozycji maszynę $M$ , która wykazuje skłonność do częstszego akceptowania słów z języka $L$ niż spoza niego. Dla słowa $x \in L$ prawdopodobieństwo akceptacji wynosi $\frac{1}{2} + α$ a odrzucenia $\frac{1}{2} - α$ . Przewaga prawdopodobieństwa wynosi $2 α$ , więc możemy mieć nadzieje, że przy odpowiednio dużej liczbie prób zdarzenie bardziej prawdopodobne będzie pojawiać się częściej.

Maszyna $M^{'}$ dla słowa wejściowego $x$ wykonuje $2 k + 1$ iteracji maszyny $M$ . Następnie daje taką odpowiedź, która występowała najczęściej. Policzmy jak prawdopodobieństwo błędu popełnianego przez maszynę $M^{'}$ zależy od $k$ .

Oprzemy dowód twierdzenia na nierówności Chernoffa znanej z rachunku prawdopodobieństwa:

Niech $x_{i}$ , dla $i = 1 \dots n$ będą niezależnymi zmiennymi losowymi przyjmującymi wartości 1 i 0 z prawdopodobieństwem odpowiednio $p$ oraz $1 - p$ , natomiast $X = \sum_{i = 1}^{n} x_{i}$ . Wówczas dla $0 \leq θ \leq 1$ zachodzi:

P (X \leq (1 - θ) p n) \leq e^{- \frac{θ^{2}}{2} p n}

Innymi słowy, prawdopodobieństwo odchylenia binarnej zmiennej losowej $X$ od jej wartości oczekiwanej maleje wykładniczo od wartości odchylenia.

Załóżmy, że $x \in L$ . Wiemy, że $P_{M} (x) \geq \frac{1}{2} + α$ . Nasze zmienne losowe $x_{i}$ to wyniki kolejnych obliczeń $M$ na słowie $x$ , prawdopodobieństwo $p$ wynosi $\frac{1}{2} + α$ , natomiast $n$ - liczba prób jest równa $2 k + 1$ . Weźmy $θ = \frac{α}{\frac{1}{2} + α}$ . Z nierówności Chernoffa mamy, że $P (X \leq \frac{n}{2}) \leq e^{- 2 α^{2} k}$ (asymptotycznie).

Wprost z definicji maszyny $M^{'}$ wiemy, że akceptuje ona, gdy ponad połowa wywołań $M$ zakończy się akceptacją, czyli wtedy, gdy $X > \frac{n}{2}$ . Jest to zdarzenie przeciwne do $X \leq \frac{n}{2}$ , zatem $P_{M^{'}} (x) \geq 1 - e^{- 2 α^{2} k}$ . Gdy podstawimy $k = ⌈ \frac{p (n) ln 2}{2 α^{2}} ⌉$ , to otrzymamy wykładnicze małe prawdopodobieństwo błędu $\frac{1}{2^{p (n)}}$ . Maszyna $M^{'}$ wykonuje tylko wielomianową liczbę powtórzeń. Przypadek $x \notin L$ jest analogiczny.

Probabilistyczne klasy złożoności

Podobnie jak dla klasy $RP$ stała $α$ może być równa nawet $\frac{1}{p (n)}$ i dalej pozwoli nam to uzyskać ten sam efekt wykładniczego ograniczenia popełnianego błędu przy zachowaniu wielomianowej liczby powtórzeń.

Powróćmy na chwilę do klasy $PP$ . Stwierdziliśmy, że dla maszyn z tej klasy prawdopodobieństwo błędu może być ograniczone przez $\frac{1}{2} - \frac{1}{2^{p (n)}}$ . Gdy przyjrzymy się dowodowi powyższego twierdzenia, to zauważymy, że aby uzyskać ten sam efekt musielibyśmy dokonać wykładniczej liczby powtórzonych obliczeń, co nie jest akceptowalne w praktyce.

Animacja Probabilistyczne klasy złożoności podsumowuje poznane wcześniej klasy złożoności i relacje pomiędzy nimi:

Rozpoznawanie liczb pierwszych

Zaznaczyliśmy na początku, że algorytmy probabilistyczne okazały się bardzo przydatne przy rozpoznawaniu liczb pierwszych. Mimo, iż w 2002 roku Agrawal, Kayal oraz Saxena odkryli wielomianowy algorytm deterministyczny dla tego problemu, wciąż używane są metody probabilistyczne, gdyż są znacznie szybsze, a prawdopodobieństwo błędu, który mogą popełnić, jest bardzo niewielkie.

Problem stwierdzenia czy liczba jest pierwsza oznaczany jest przez PRIMES. W sposób oczywisty jest to problem z klasy $coNP$ . Dzieje się tak ze względu na fakt, że łatwo jest poświadczyć, iż liczba nie jest pierwsza, poprzez podanie jej dzielników.

Podobnie, choć nie z tej samej przyczyny, znane metody probabilistyczne opierają się na algorytmach z klasy $coRP$ . Opierają się one na poświadczeniu złożoności liczby, które nie polega jednak na podawaniu jej dzielników (problem faktoryzacji jest bowiem dużo trudniejszy).

Jak wymaga tego klasa $coRP$ , odpowiedź negatywna jest zawsze prawdziwa, natomiast mogą występować fałszywe odpowiedzi pozytywne. Poprzez odpowiednio dużą liczbę iteracji prawdopodobieństwo takiego faktu można uczynić dowolnie małym. Podsumowując, probabilistyczne testy pierwszości mogą popełnić błąd oceniając liczbę złożoną jako pierwszą.

Test Millera-Rabina

Poniżej prezentujemy najbardziej znany z testów probabilistycznych odkryty niezależnie przez Gary'ego Millera i Michaela Rabina około roku 1975. Na wejściu dana jest liczba naturalna $n$ . Jedna iteracja algorytmu przedstawia się następująco:

Algorytm

Przedstaw  $n - 1$  jako  $2^{s} d$ , d - nieparzysta 
Wybierz losową liczbę  $a$  z przedziału  $[1, n - 1]$  
if  $a^{d}$  mod   $n \neq 1$  i  $a^{2^{r} d}$   mod   $n \neq - 1$  dla wszystkich  $r \in [0, s - 1]$   then
  return""NIE"" 
else 
  return""TAK"" 
end if

Gdy przypatrzymy się algorytmowi, to widzimy, że kluczem do sukcesu jest wylosowanie właściwej liczby $a$ , która poświadcza złożoność $n$ . W takim przypadku algorytm się nie myli - można bowiem udowodnić (patrz kurs Matematyki Dyskretnej), że sprawdzany warunek implikuje złożoność liczby $n$ .

Jeśli $a$ nie świadczy złożoności, to możemy spróbować wylosować je jeszcze raz. Niestety nie możemy spróbować wszystkich możliwych wartości $a$ , których liczba jest liniowa względem $n$ , czyli wykładnicza względem rozmiaru wejścia, które tradycyjnie zapisujemy binarnie.

Jeśli $n$ jest pierwsza, to oczywiście świadek $a$ nie istnieje. Poniższe twierdzenie, które przedstawiamy bez dowodu, stanowi teoretyczną podstawę analizy probabilistycznej algorytmu:

Twierdzenie 2.1.

Jeśli $n$ jest nieparzystą liczbą złożoną, to przynajmniej $\frac{3}{4}$ spośród możliwych wartości $a$ świadczą o złożoności $n$ .

Jeśli poprzez $M$ oznaczymy maszynę realizującą pojedynczy test Millera-Rabina, a poprzez $L$ język PRIMES, to nasze dotychczasowe uwagi możemy podsumować w sposób następujący:

$x \in L$ ( $n$ pierwsza) $\Rightarrow P_{M} (x) = 1$ ,
$x \notin L$ ( $n$ złożona) $\Rightarrow P_{M} (x) \leq \frac{1}{4}$ .

Spełnione są zatem założenia algorytmu z klasy $coRP$ . Gdy otrzymujemy odpowiedź ""NIE"", to liczba jest złożona, gdy otrzymujemy odpowiedź ""TAK"", to liczba jest pierwsza z prawdopodobieństwem błędu $\frac{1}{4}$ . Gdy wykonamy $k$ iteracji, to gdy w którymkolwiek momencie otrzymamy odpowiedź ""NIE"", to liczba jest złożona, w przeciwnym razie jest pierwsza z prawdopodobieństwem błędu ograniczonym przez $\frac{1}{4^{k}}$ , czyli wykładniczo małym.

Co interesujące, Miller przedstawił ten test w wersji deterministycznej, w której podstawa $a$ przebiega przedział o wielkości $O ($ ln $2 (n))$ . Stąd potrzebna liczba iteracji testu jest wielomianowa. Nie ma jednak dowodu, że takie postępowanie jest prawidłowe. Poprawność tego podejścia wynika jednak z rozszerzonej hipotezy Riemanna. Ten fakt sprawia, że test Millera-Rabina jest w pewnym sensie "zabezpieczony podwójnie".

Generowanie bitów losowych

Kluczowym elementem praktycznych realizacji opisywanych do tej pory algorytmów probabilistycznych jest losowanie. Okazuje się, że teoretycznie prosty rzut monetą to bardzo wymagający problem praktyczny.

Generowanie bitów losowych w teorii, to zadanie polegające na obliczeniu ciągu $n$ bitów tak, aby każdy z ciągów był jednakowo prawdopodobny, czyli aby każdy bit zachowywał się jak niezależna próba losowa. Źródło, które generuje taki ciąg nazywamy idealnym.

Mając do dyspozycji źródło idealne moglibyśmy z powodzeniem używać algorytmów z klasy $RP$ , czy $BPP$ w praktycznych zastosowaniach. Niestety nie jest znane idealne fizyczne źródło bitów losowych. Choć istnieją lepsze i gorsze metody generowania losowych bitów, to każdy proces fizyczny wykazuje tendencję do uzależnienia kolejnych wartości od wcześniej występujących, co zaburza pożądaną przez nas niezależność.

Idealne źródło bitów losowych jest także symetryczne, to znaczy prawdopodobieństwo 0 i 1 w każdym kroku jest jednakowe. Tę własność można jednak stosunkowo łatwo uzyskać, przez grupowanie kolejnych prób.

W praktyce często stosuje się generatory bitów pseudolosowych, które generują ciągi bitów "nieprzewidywalnych". Zwykle jednak rozpoczynają one obliczenia od ziarna złożonego z niewielkiej liczby bitów, co z teoretycznego punktu widzenia jest dyskwalifikujące.

W literaturze wyróżnia się także źródła lekko losowe, które dosyć dobrze opisują dostępne w praktyce wysoce losowe zjawiska fizyczne. Nie jest niestety znana metoda symulowania przy ich pomocy idealnych źródeł losowych. Mogą one być jednak zastosowane do symulowania znanych nam algorytmów losowych z wielomianowym wzrostem czasu. Powyższy temat znajduje osobne miejsce w analizie teoretycznej algorytmów probabilistycznych.

Ćwiczenia dodatkowe

Ćwiczenie 4.1.

Uzasadnij, że klasy $BPP$ oraz $PP$ są zamknięte na dopełnienie.

Wskazówka

Rozwiązanie

Przeprowadźmy najpierw dowód dla klasy $BPP$ . Weźmy dowolny język $L \in BPP$ . Załóżmy, że jest on akceptowany przez maszynę probabilistyczną $M$ . Rozważmy $\overline{L}$ i pokażmy, że należy on do $BPP$ . Maszyna, która będzie dla niego odpowiednia, to $M$ z odwróconymi odpowiedziami, którą oznaczamy przez $M^{'}$ .

Jeśli $x \in \overline{L}$ , to $x \notin L$ , zatem $P_{M} (x) \leq \frac{1}{4}$ , stąd $P_{M^{'}} (x) \geq \frac{3}{4}$ . Podobnie jeśli $x \notin \overline{L}$ , to $x \in L$ , zatem $P_{M} (x) \geq \frac{3}{4}$ ,stąd $P_{M^{'}} (x) \leq \frac{1}{4}$ . Maszyna $M^{'}$ spełnia zatem warunki klasy $BPP$ .

Przypadek klasy $PP$ jest analogiczny. Weźmy $L \in PP$ i maszynę $M$ dla niego. Załóżmy, że maszyna $M$ dla każdego wejścia nie posiada remisu w liczbie ścieżek akceptujących i odrzucających (zapewniamy to prostą modyfikacją nie zmieniającą języka maszyny). Pokażmy, że $\overline{L}$ jest akceptowany przez $M^{'}$ , która ponownie jest maszyną $M$ z odwróconymi odpowiedziami. Jeśli $x \in \overline{L}$ , to $x \notin L$ , zatem $P_{M} (x) < \frac{1}{2}$ , stąd $P_{M^{'}} (x) > \frac{1}{2}$ . Podobnie jeśli $x \notin \overline{L}$ , to $x \in L$ , zatem $P_{M} (x) > \frac{1}{2}$ , stąd $P_{M^{'}} (x) < \frac{1}{2}$ . Maszyna $M^{'}$ spełnia zatem warunki klasy $PP$ .

Ćwiczenie 4.2.

Pokaż, że $PP \subseteq PSPACE$

Wskazówka

Skonstruuj maszynę odpowiednią dla $PSPACE$ na podstawie maszyny dla klasy $PP$

Rozwiązanie

Weźmy język $L \in PP$ i maszynę probabilistyczną $M$ dla niego. Maszyna działa w czasie wielomianowym, więc potencjalna liczba wszystkich ścieżek jest wykładnicza. Możemy jednak zastosować standardowy zabieg polegający na analizie każdej ścieżki obliczeń (długości wielomianowej) w tej samej pamięci - w ten sposób konstruujemy maszynę $M^{'}$ z klasy $PSPACE$ . Musimy jedynie pamiętać wektor kolejnych wyborów (również długości wielomianowej), aby móc wygenerować następny z nich.

Dla słowa wejściowego $x$ zliczamy ile spośród ścieżek obliczeń $M$ jest akceptujących. Jeśli więcej niż połowa, to akceptujemy słowo, w przeciwnym wypadku odrzucamy.

Pokażmy, że maszyna $M^{'}$ akceptuje język $L$ . Jeśli $x \in L$ , to $P_{M} (x) > \frac{1}{2}$ , stąd ponad połowa ścieżek $M$ akceptuje $x$ , więc również $M^{'}$ zaakceptuje $x$ . Podobnie jeśli $x \notin L$ , to $P_{M} (x) \leq \frac{1}{2}$ , stąd co najwyżej połowa ścieżek $M$ akceptuje $x$ , więc $M^{'}$ odrzuci $x$ .

Ćwiczenie 4.3.

Pokaż, że jeśli $NP \subseteq BPP$ , to $RP = NP$

Wskazówka

Rozwiązanie

Jeśli $NP \subseteq BPP$ , to SAT należy do $BPP$ . Pokażmy, że wtedy SAT należy do $RP$ , a ponieważ jest zupełny dla $NP$ , to stąd otrzymamy, że $NP \subseteq RP$ (zawieranie się w drugą stronę jest prawdziwe zawsze).

Weźmy maszynę probabilistyczną $M$ z klasy $BPP$ dla SAT. Na jej podstawie skonstruujemy maszynę $M^{'}$ dla SAT, ale z klasy $RP$ .

Ustalmy formułę wejściową $ϕ$ o $n$ zmiennych. Maszyna $M^{'}$ będzie w pierwszej części próbować obliczyć wartościowanie spełniające $ϕ$ przy pomocy maszyny $M$ . Będziemy używać wersji $M$ , która ma prawdopodobieństwo błędu ograniczone przez $\frac{1}{2 n}$ , co możemy uczynić na podstawie omawianego już twierdzenia o ograniczaniu prawdopodobieństwa błędu dla klasy BPP.

Maszyna $M^{'}$ rozpoczyna działanie od sprawdzenia (przy pomocy $M$ ), czy $ϕ$ jest spełnialna. Jeśli odpowiedź brzmi ""NIE"", to $M^{'}$ również odrzuca. Następnie kolejno ustalamy wartości zmiennych $x_{i}$ . Rozpoczynamy od $x_{1}$ ustawionego na 0. Uruchamiamy algorytm $M$ dla formuły $ϕ$ z tak ustalonym $x_{1}$ . Jeśli $M$ twierdzi, że jest ona spełnialna, to pozostawiamy $x_{1} = 0$ , w przeciwnym wypadku wybieramy $x_{1} = 1$ . Postępujemy tak, ustalając wartości wszystkich zmiennych.

W drugiej fazie działania $M^{'}$ sprawdzamy bezpośrednio, czy $ϕ$ na tak obliczonym wartościowaniu okazuje się być spełnialna i jeśli tak to $M^{'}$ ostatecznie akceptuje, a w przeciwnym wypadku odrzuca.

Przejdźmy do analizy $M^{'}$ . Jeśli formuła $ϕ$ (kodowana przez $x$ )nie jest spełnialna, to $P_{M^{'}} (x) = 0$ , gdyż bez względu na wszystko, w drugiej fazie swojego działania $M^{'}$ sprawdza czy dostała poprawne wartościowanie.

Jeśli natomiast $ϕ$ jest spełnialna, to obliczmy z jakim prawdopodobieństwem na końcu znajdziemy poprawne wartościowanie, które spowoduje akceptację. Aby nam się udało, to musimy podczas każdego z $n$ wyborów wartościowań $x_{i}$ nie popełnić błędu. Prawdopodobieństwo zdarzenia przeciwnego (czyli przynajmniej jeden błąd) może być ograniczone przez $n \frac{1}{2 n} = \frac{1}{2}$ , zatem $P_{M^{'}} (x) \geq \frac{1}{2}$ . Stąd nasz algorytm spełnia warunki klasy $RP$ .

Złożoność obliczeniowa/Wykład 10: Algorytmy probabilistyczne

Spis treści