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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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 jest zwykłą niedeterministyczną maszyną Turinga. Przypomnijmy, że ma podczas każdego kroku obliczeń możliwość wyboru wielu ścieżek obliczeń. W pojęciu akceptacji słowa bierzemy pod uwagę zachowanie 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 wybiera spośród dwóch możliwości wyboru ścieżki. Wyobraźmy sobie, że maszyna 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 nazywamy probabilistyczną. Maszyna probabilistyczna akceptuje słowo wejściowe 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 i słowa wejściowego definiujemy jako prawdopodobieństwo, że maszyna zaakceptuje słowo .

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 , jej języka i słowa wejściowego zachodzi zatem:

Naszym obiektem zainteresowania jest powiązanie prawdopodobieństwa akceptacji słowa z jego przynależnością do konkretnego języka . W ten sposób będziemy mogli używać maszyny probabilistycznej do akceptowania 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 może być dwojakiego rodzaju. Ustalmy . Jeśli to akceptuje z prawdopodobieństwem . Jeśli nie jest ono równe 1, to może się okazać, że odrzuci . Mówimy wtedy o fałszywej odpowiedzi negatywnej. Maszyna odrzuca poprawne słowo z języka !

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

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 ]]

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

  • ,
  • .

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

Wyobraźmy sobie, że mamy język z klasy i maszynę dla niego. Uruchamiamy na . 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 .

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 . W tym momencie wykonujemy jednak genialny w swojej prostocie manewr - uruchamiamy 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 .

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 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.

Monte Carlo

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 w definicji klasy nie ma żadnego znaczenia i wystarczy nam, żeby była dodatnia:

Ćwiczenie 1.3.

Pokaż, że stała w definicji klasy może zostać zamieniona na dowolną stałą z przedziału lub nawet zależeć od poprzez , gdzie jest wielomianem.

Wskazówka
Rozwiązanie

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

Ćwiczenie 1.4.

Pokaż, że .

Wskazówka
Rozwiązanie

Maszyny z klasy 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ą , 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 daje odpowiedź ""NIE"" to słowo na pewno do języka nie należy. Natomiast prawdopodobieństwo fałszywej odpowiedzi pozytywnej jest ograniczone przez . Wszystkie własności są dualne, w szczególności .

Definicja 1.5. [Klasa ]

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

  • .
  • ,

Klasa

Odpowiedź na pytanie, czy nie jest znana. Bez tej odpowiedzi możemy jednak rozważyć klasę . 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ć prób obu algorytmów wynosi , czyli maleje wykładniczo.

Las Vegas

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 ]

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

Nietrudno pokazać, że . 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

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

Definicja 1.7. [Klasa ]

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

  • ,
  • .

Ponieważ występujące w definicji prawdopodobieństwo błędu może być dowolnie bliskie , 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 tylko o , gdzie 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 to w sytuacji odchylenia będziemy musieli wykonać wykładniczą liczbę powtórzeń, aby uzyskać prawdopodobieństwo błędu ograniczone przez . Prześledzimy to dokładnie w następnym rozdziale, w którym rozważana klasa będzie mieć prawdopodobieństwo błędu oddalone od o stałą.

Taka sytuacja sprawia, że odpowiedź maszyny z klasy 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 , to maszyna nie różni się niczym od pojedynczego rzutu monetą, który nie niesie żadnej informacji o języku . To wszystko sprawia, że maszyny z klasy 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

Wskazówka
Rozwiązanie

Rozważmy następujący problem:

Definicja 1.9.

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

Ćwiczenie 1.10

Pokaż, że MAJSAT należy do .

Wskazówka
Rozwiązanie

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

Klasa

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

Definicja 1.11 [Klasa ]

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

  • ,
  • .

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

Patrząc na definicję klasy 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 . Podobnie jak dla klasy ta stała może zostać wybrana dowolnie z przedziału , lecz jest to fakt trudniejszy:

Twierdzenie 1.12

Niech . Dla dowolnej maszyny probabilistycznej działającej w czasie wielomianowym, o prawdopodobieństwie błędu ograniczonym przez , istnieje równoważna wielomianowa maszyna probabilistyczna o prawdopodobieństwie błędu ograniczonym przez , gdzie jest wielomianem.

Dowód

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

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

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

Niech , dla będą niezależnymi zmiennymi losowymi przyjmującymi wartości 1 i 0 z prawdopodobieństwem odpowiednio oraz , natomiast . Wówczas dla zachodzi:

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

Załóżmy, że . Wiemy, że . Nasze zmienne losowe to wyniki kolejnych obliczeń na słowie , prawdopodobieństwo wynosi , natomiast - liczba prób jest równa . Weźmy . Z nierówności Chernoffa mamy, że (asymptotycznie).

Wprost z definicji maszyny wiemy, że akceptuje ona, gdy ponad połowa wywołań zakończy się akceptacją, czyli wtedy, gdy . Jest to zdarzenie przeciwne do , zatem . Gdy podstawimy , to otrzymamy wykładnicze małe prawdopodobieństwo błędu . Maszyna wykonuje tylko wielomianową liczbę powtórzeń. Przypadek jest analogiczny.

End of proof.gif

Podobnie jak dla klasy stała może być równa nawet 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 . Stwierdziliśmy, że dla maszyn z tej klasy prawdopodobieństwo błędu może być ograniczone przez . 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 . 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 . 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 , 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 . Jedna iteracja algorytmu przedstawia się następująco:

Algorytm


Przedstaw  jako , d - nieparzysta 
Wybierz losową liczbę  z przedziału  
if  mod   i   mod   dla wszystkich   then
  return""NIE"" 
else 
  return""TAK"" 
end if


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

Jeśli 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 , których liczba jest liniowa względem , czyli wykładnicza względem rozmiaru wejścia, które tradycyjnie zapisujemy binarnie.

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

Twierdzenie 2.1.

Jeśli jest nieparzystą liczbą złożoną, to przynajmniej spośród możliwych wartości świadczą o złożoności .

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

  • ( pierwsza) ,
  • ( złożona) .

Spełnione są zatem założenia algorytmu z klasy . Gdy otrzymujemy odpowiedź ""NIE"", to liczba jest złożona, gdy otrzymujemy odpowiedź ""TAK"", to liczba jest pierwsza z prawdopodobieństwem błędu . Gdy wykonamy 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 , czyli wykładniczo małym.

Co interesujące, Miller przedstawił ten test w wersji deterministycznej, w której podstawa przebiega przedział o wielkości ln . 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 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 , czy 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 oraz są zamknięte na dopełnienie.

Wskazówka
Rozwiązanie

Ćwiczenie 4.2.

Pokaż, że

Wskazówka
Rozwiązanie

Ćwiczenie 4.3.

Pokaż, że jeśli , to

Wskazówka
Rozwiązanie

Testy końcowe