Zreformował nasze rozumienie roli losowości w obliczeniach. Avi Wigderson otrzymał Nagrodę Turinga

Świat stawia przed nami wiele wyzwań obliczeniowych, które kategoryzuje się wedle ich trudności. O kilku konkretnych kategoriach będzie tu mowa, ale jest wiele, wiele innych.

Najłatwiejsze są problemy klasy P. Dla nich znamy efektywne algorytmy generowania i weryfikacji pożądanych właściwości, bez wykorzystania losowości i przeglądania przesadnie dużych ilości możliwości.

W środku skali znajdują się problemy trudne, ale mające jedną niezmiernie pożyteczną dla nas cechę: wiemy, że jeśli chciane przez nas rozwiązania w ogóle istnieją, to jest ich stosunkowo wiele, oraz że potrafimy wydajnie oceniać ich jakość. Wówczas pojawia się szansa wykorzystania w obliczeniach losowości. Polega to na odpowiednio dobranej, sprytnej metodzie losowania, żeby z jakimś prawdopodobieństwem, powiedzmy 1‰, dostać dostatecznie dobre rozwiązanie. Oczywiście to niewielka szansa, ale powtarzając losowanie 7 tys. razy, ryzyko, że żadne nie będzie dobre mamy już tylko na poziomie dużo poniżej 1. A jeśli jednak żadne nie będzie dobre, to z takim właśnie ryzykiem można uznać, że to, czego szukamy, nie istnieje. Tak można na przykład wybierać liczby pierwsze, które są bardzo przydatne w powszechnie stosowanych metodach szyfrowania.

Wiadomo, że zawsze pomiędzy liczbą n a liczbą 2n jest jakaś liczba pierwsza. Przeglądanie ich jedna po drugiej jest ryzykowne, bo pomiędzy kolejnymi zdarzają się bardzo długie luki. Z kolei z badań nad liczbami pierwszymi wiadomo, że w tym przedziale jest ich ok. n/ ln n, czyli szansa trafienia przy losowaniu na jedną z nich wynosi ponad 1/ ln n. A to zazwyczaj już całkiem dużo – na przykład dla realnie używanych kluczy RSA to by było nawet lepiej niż 1‰. To wystarczy, żeby z ogromnym prawdopodobieństwem znaleźć którąś z nich.

Klasa problemów mających te dobre cechy często jest oznaczana jako BPP. Tutaj wpadają wszystkie problemy rozwiązywane metodami Monte Carlo. Pewnym cieniem kładzie się na BPP to, że w praktyce nie mamy gwarantowanego źródła losowości, praktycznie musimy się zadowalać liczbami pseudolosowymi. Z jednej strony, mamy wtedy do czynienia z algorytmami w klasie P, które naprawdę nic nie losują, tylko deterministycznie generują liczby zaledwie wyglądające na losowe. Z drugiej strony, ich niepełna losowość może wpływać na poprawność algorytmów, której dowodzimy teoretycznie, zakładając prawdziwą losowość tam, gdzie w praktyce używamy jej taniej imitacji.

Do najtrudniejszych problemów, o których chcę tutaj napisać, należą te z klasy E, wśród których praktycznymi przedstawicielami są: układanie wystarczająco najlepszych planów zajęć dla szkół, najlepszych planów podróży dla komiwojażerów albo przydziałów pasm częstotliwości dla nadajników, które nie powinny się nawzajem zakłócać. Trudność zadania bierze się stąd, że potencjalnych rozwiązań jest niezmiernie dużo, a ogromna większość ma jakieś wady – znalezienie prawidłowego to szukanie igły w stogu siana. Jednak algorytmy w klasie E mogą przekopywać się przez niego do skutku. Mając prawo ich użyć do znajdowania liczb pierwszych, moglibyśmy na przykład przejrzeć wszystkie liczby od n do 2n i wziąć spośród znalezionych liczb pierwszych taką, która nam się najbardziej będzie podobała.

I teraz o odkryciu, w którym poważny udział brał Avi Wigderson.

Ono zaczyna się od obserwacji, że algorytm w BPP, który wykorzystuje tylko generator liczb pseudolosowych, jest naprawdę algorytmem z klasy P. Gdybyśmy zatem potrafili tworzyć naprawdę dobre generatory liczb pseudolosowych, czyli na pewno niezaburzające poprawności algorytmów, to okazałoby się, że potrafimy derandomizować algorytmy używające losowości, a w konsekwencji, że klasy P i BPP są takie same.

Avi Wigderson i Russel Impagliazzo udowodnili, że jeśli są problemy z klasy E, których obliczeń nie da się przybliżać za pomocą obwodów logicznych rozmiaru wielomianowego (pomyślmy o nich, jako specjalnie budowanych procesorach o rozsądnym rozmiarze – do danych każdego rozmiaru mamy prawo mieć osobny, zupełnie inny procesor), to istnieją wystarczająco dobre i szybkie generatory liczb pseudolosowych, używające małego naprawdę losowego ziarna, których żaden algorytm wielomianowy nie umie wystarczająco dobrze odróżniać od losowych. A skoro nie umie, to znaczy, że jego wyniki na danych pseudolosowych nie odbiegają znacząco od wyników na danych prawdziwie losowych, czyli: co było poprawne w teorii zakładającej pełną losowość, pozostaje poprawne w praktycznej realizacji za pomocą generatora pseudolosowego. Został tylko problem małego ziarna losowego. Z tym z kolei można sobie poradzić tak, że sprawdza się wszystkie ziarna – są na tyle małe, że w klasie P daje się je wszystkie przejrzeć. Sumuje się wynikające z obliczeń prawdopodobieństwa dla każdego ziarna i okazuje się, że sumaryczny błąd wynikający z niepełnej losowości obliczeń dla poszczególnych ziaren nie jest na tyle duży, żeby zakłócić wynik.

W swojej książce „Mathematics and Computation A Theory Revolutionizing Technology and Science” Wigderson uznał, że to sytuacja, w której oglądamy niezwykły typ wynikania: jeśli jedna klasa problemów obliczeniowych (E w tym wypadku) jest bardzo trudna, to – niejako dla pocieszenia – klasa BPP jest łatwa, bo okazuje się zawarta w P. Ja tak tego nie widzę, dla mnie to wynik bardzo pesymistyczny: jeśli E jest bardzo trudna, to – co gorsza – nie jesteśmy w stanie sobie pomóc w walce z trudnymi obliczeniowo problemami, używając losowości, bo ona żadnej nowej jakości w porównaniu do P nie daje. Dla pełnego zrozumienia sytuacji wypada dodać, że to wszystko są wyniki wysoce teoretyczne, które na współczesną jawną praktykę programowania nie wydają się mieć istotnego wpływu. Zastrzeżenie o jawności jest o tyle istotne, że istnienie tak dobrych generatorów liczb pseudolosowych jest powiązane z istnieniem trudnych do wydajnego łamania szyfrów. A badania nad tym niewątpliwie są prowadzone w głębokiej tajemnicy w wielu miejscach na świecie, bo nikogo nie stać na ponoszenie ryzyka, żeby ich w tej dziedzinie wyprzedzili inni.

Zdaję sobie sprawę, że w zasadzie tylko akapit powyżej opisuje dokonanie Wigdersona, jedno wybrane z bardzo wielu będących jego dziełem. Docenia się jego znaczenie dopiero wtedy, kiedy zna się kontekst. Dlatego napisałem tych akapitów o wiele więcej z nadzieją, że mi to P.T. Czytelnicy wybaczą.