Jak zarobić milion dolarów, czyli potęga algorytmu

Pytania muszą być tak sformułowane, żeby odpowiedź brzmiała "tak" albo "nie". Dla uniknięcia sporów znanych graczom scrabble'a, typu "czy istnieje słowo bdździągwa?", zwykle wprowadzany jest dodatkowy warunek: odgadywana rzecz musi być do odnalezienia w jakimś słowniku czy encyklopedii.

W różne warianty tej gry grają bohaterowie "Opowieści wigilijnej" Dickensa i "Bękartów wojny" Tarantino. W tym ostatnim przypadku pytań jest tylko dziewięć, ale nie chodzi o przedmioty, tylko o sławne osoby.

Gra dostarcza dużo zabawy całemu towarzystwu, bo pytania typu: "Czy to się rusza?" albo "Czy to można zjeść?", potrafią prowadzić do zaskakujących skojarzeń, kiedy odgadywanym obiektem jest strzykwa albo kandelabr. Dlatego w wielu krajach teleturniej według tej formuły nadawany jest od pierwszych lat telewizji aż po czasy najnowsze.

I tylko w Polsce całą zabawę zepsuło trzech matematyków: Aleksander Pełczyński, Wiesław Szlenk i Robert Bartoszyński, którzy we wrześniu 1962 wystąpili w tym programie w TVP i zastosowali do jego wygrania algorytm bisekcji. Niestety, nie zachowała się rejestracja tego programu, bo wtedy telewizja była robiona na żywo, a był to jeden z historycznych momentów w dziejach TVP.

W ówczesnej ramówce ostatnia niedziela miesiąca była zarezerwowana na teleturniej. Po występie matematyków program trzeba było zdjąć z anteny, bo wiedza o tym, jak wygrać w tym teleturnieju, dotarła pod strzechy.

Przez cały październik przygotowywano formułę programu, który zastąpi "20 pytań", i udało się to nadspodziewanie dobrze. Prowadzący "20 pytań" Ryszard Serafinowicz wykorzystał okazję, żeby zamiast zwykłego teleturnieju zrobić edukacyjne cacko - "Wielką grę", którą pierwszy raz nadawano w listopadzie 1962 r. (i dotrwała do 2006 r., gdy w ramach misji dekomunizacyjnej zdjął ją z anteny ówczesny prezes Bronisław Wildstein).

W ten sposób występ matematyków przyczynił się do rozwoju polskiej produkcji telewizyjnej. Miał też niebagatelny wpływ na edukację - na Uniwersytecie Warszawskim dr Piotr Chrząstowski-Wachtel odwołuje się do tego przykładu, demonstrując adeptom informatyki potęgę algorytmu bisekcji.

Teleturniej rozpracowany

Jak zastosować ten algorytm do zabawy w "20 pytań"? Załóżmy, że podstawą słownikową do gry jest dziesięciotomowy "Wielki słownik języka polskiego" (dla uproszczenia pomińmy suplement). Powiedzmy, że odgadywanym słowem jest właśnie "algorytm".

Pierwsze pytanie powinno brzmieć: "Czy to słowo jest w pierwszych pięciu tomach słownika"? Odpowiadamy: "tak". Potem: "Czy jest w pierwszych dwóch tomach słownika"? Kolejne "tak".

Po chwili już wiemy, że jesteśmy w pierwszym tomie. Wtedy dalej zawężamy obszar poszukiwań, za każdym razem starając się dzielić obszar niepewności mniej więcej na pół (stąd nazwa "bisekcja").

Po chwili już wiemy, na której jesteśmy stronie. I na której połowie tej strony. I w której ćwiartce. Wreszcie mamy wyszukiwanie zawężone do kilku słów, a na koniec zostają nam dwa do wyboru.

Oczywiście, ten sposób rozwiązania zagadki w ogóle nie jest zabawny. Za to jest pieruńsko skuteczny - wynik powinniśmy dostać po najdalej 18 pytaniach, dlatego żeby nie było zbyt nudno, to pierwsze może być kompletnie od czapy (podobno we wrześniu 1962 r. pierwsze pytanie matematyków brzmiało: "Czy to jest żaba?").

Dlaczego? Bo liczba kroków potrzebnych do rozwiązania tego algorytmu rośnie bardzo wolno - logarytmicznie - razem z przyrostem opcji do wyboru. Co to znaczy?

Do wyboru jednej z dwóch opcji potrzebujemy, naturalnie, jednego pytania. Do jednej z czterech - dwóch pytań. Do jednej z ośmiu - trzech. I tak dalej. 20 pytań wystarcza na odnalezienie właściwej odpowiedzi wśród przeszło miliona opcji. "Wielki słownik języka polskiego" opracowany pod redakcją prof. Witolda Doroszewskiego ma tylko 110 tysięcy haseł. We właściwe słowo trafimy po najwyżej 17 próbach. Dwunastotomowa "Wielka encyklopedia powszechna" ma 141 tysięcy haseł. To o 30 tysięcy haseł więcej - sporo, wystarczy na dwa, trzy dodatkowe tomy! - ale logarytm ledwie to zauważa. Teraz potrzebne będzie co najwyżej 18 pytań, aby trafić właściwe hasło.

Logarytm słynie z tego, że jego wartość rośnie bardzo powoli (żeby mieć jeszcze wolniejszą funkcję, musimy kombinować z udziwnieniami typu "logarytm logarytmu"), dlatego informatyk zawsze cieszy się, gdy udaje mu się napisać program, którego czas wykonywania będzie rosnąć logarytmicznie razem ze złożonością problemu. Każdy problem, który uda się sprowadzić do algorytmu bisekcji, jest rozwiązany po wsze czasy.

Ilekroć zdumiewa nas potęga wyszukiwarek takich jak Google, które w ułamku sekundy odnajdują dla nas odpowiedź, nie podziwiajmy potęgi komputerów Google'a. Podziwiajmy talent informatyków, którzy zręcznie wykorzystali bisekcję.

Same algorytmy Google'a są oczywiście tajemnicą firmy, podobnie jak algorytm, za pomocą którego Facebook rozpoznaje nasze twarze albo algorytm, którym Spotify wyszukuje piosenki podobne do tej, której właśnie słuchamy. Ale żeby to w ogóle mogło działać, prawie na pewno gdzieś w samym środku tego programu ma miejsce bisekcja.

zbudowaliśmy coś, co właśnie wymyka nam się z rąk? Algorytmy rządzą światem

 

Zwróćmy uwagę, że do wyszukiwania metodą bisekcji nie potrzebujemy geniusza. Z całym szacunkiem dla matematyków, którzy zmienili historię TVP - ich algorytmem może się posłużyć każdy głupi. Nie obrażam tym ich pamięci, przeciwnie, właśnie na tym polega istota algorytmu: zagadnienie pozornie bardzo złożone zostaje sprowadzone do serii regułek, które może realizować każdy. Nawet komputer.

Komputery wydają nam się bardzo mądre, ale jest inaczej. Są bardzo głupie. Wszystko, co robią, zawdzięczają talentowi informatyków, którzy coraz bardziej skomplikowane problemy potrafią sprowadzić do odpowiedniego algorytmu.

czy powiedzielibyście: ''Jestem analfabetą. W pierwszej klasie sylaby wywołały u mnie taką traumę, że nigdy nie nauczyłem się dobrze czytać i pisać''? Matematyczni analfabeci

Kto zna algorytm, ten ma władzę

W średniowieczu algorytmy były wiedzą tajemną. Matematycy, którzy poznali ten sekret, górowali nad kolegami, którzy musieli coś mozolnie liczyć na piechotę. Zdradzenie się z tą wiedzą nie zawsze było jednak bezpieczne.

Dlaczego? Bo algorytm, tak jak alkohol czy alembik, jest słowem pochodzenia arabskiego.

To zniekształcone przez hiszpańskie zapożyczenie arabskie Al-Chuwarizmi - przydomek perskiego uczonego, którego pełna pisownia nazwiska to Abu Abdullah Muhammad ibn Musa al-Chuwarizmi. Stworzył on na początku IX wieku w Bagdadzie księgę zatytułowaną "Kompendium o obliczaniu przy pomocy dopełniania i równoważenia". Za jego sprawą algebrę nazywamy od tytułu tej książki ("al-dżabr" to "dopełnianie").

Książka zawierała serię porad na szybkie znalezienie rozwiązania równań kwadratowych, jeśli tylko sprowadzimy je do postaci, po której możemy już skorzystać z gotowych wzorców (na przykład znanego ze szkoły ax2 + bx = c). Sprowadzanie do tej formuły to właśnie tytułowe "dopełnianie i równoważenie". A potem już z górki. Po prostu podstawiamy a, b i c do formułek, których nawet nie musimy zapamiętywać (po opuszczeniu szkoły).

Wystarczy ściąga i umiejętność skorzystania z niej. Kompendium Al-Chuwarizmiego było właśnie taką uniwersalną ściągą.

Europejska matematyka oswajała się z algebrą i algorytmami powoli, bo nigdy nie było wiadomo, czy inkwizycja spojrzy przychylnie na to, że ktoś interesuje się tajną wiedzą z arabskich ksiąg. Jednak algorytmy - bez używania tego słowa - znali już starożytni Grecy.

Przełamali kompleks Polaków w naukach ścisłych. Genialni z kawiarni Szkocka

 

Euklides na przykład zostawił przepis na szukanie największego wspólnego dzielnika dwóch liczb (do dziś dzieci uczą się go w szkole). W algorytmie Euklidesa liczba kroków rośnie proporcjonalnie do rozmiarów liczb, czyli liniowo, jak powie matematyk. Zależność liniowa to przypadek gorszy od zależności logarytmicznej, ale informatyka ciągle jeszcze potrafi z nim sobie dać radę.

Typowy przykład zagadnienia o liniowej zależności to szukanie informacji w nieposortowanej bazie danych. Zauważmy, że powyższy przepis na wygraną w teleturnieju "20 pytań" zawierał pewne sprytne oszukaństwo - ktoś za nas (np. zespół profesora Doroszewskiego) wykonał tytaniczną pracę ułożenia słownika alfabetycznie.

Algorytm bisekcji będzie bezradny w przypadku słownika potasowanego, czyli takiego, co do którego wprawdzie wiemy, że zawiera słowo "algorytm", ale nie mamy pojęcia, w którym tomie. Oczywiście, nikt przy zdrowych zmysłach nie tasuje słowników, ale w praktyce często spotykamy się z niepoukładanymi zbiorami danych.

W informatyce przykładem są staroświeckie systemu zapisu danych, do dzisiaj używane m.in. na pendrive'ach, a w świecie fizycznym: biblioteka, w której książki poustawiano przypadkowo na półkach. Wtedy nie ma zmiłuj, trzeba po prostu metodycznie przeglądać zapis po zapisie, aż się znajdzie ten właściwy. I będzie to trwało tym dłużej, im więcej ich jest.

Przełamał kompleks Polaków w naukach ścisłych. Genialny matematyk, o którym mówiono, że "przepijał do każdego"

Jak w Monte Carlo

Szukanie w nieposortowanym zbiorze należy do ogólnej klasy algorytmów, nazywanej fachowo "algorytmami klasy P". P to skrót od angielskiego określenia na "wielomian" ("polynomial"). Bo czas ich wykonania daje się opisać jakimś wielomianem zależnym od wielkości danych. W najprostszym (i dość częstym) przypadku - zależność jest liniowa, bo najprostszy wielomian to po prostu funkcja liniowa.

Jeśli zrozumieli państwo powyższe dwa akapity, to połowa przepisu na milion dolarów już jest za nami. Ta połowa to definicja "algorytmu klasy P". Druga połowa to "algorytm klasy NP".

Do tej klasy należą takie algorytmy, w których zależność wielomianowa dotyczy innego przypadku: sprawdzenia poprawności losowej odpowiedzi. Czyli po prostu przypadkowego strzału, np. jak w przypadku naszych matematyków i ich pytania "czy to jest żaba?".

Oczywiście, tak się nie da rozwiązać zabawy w "20 pytań", ale takie strzały z biodra są uznaną w matematyce metodą rozwiązywania zagadnień, których z jakiegoś powodu nie da się rozwiązać inaczej. Polski matematyk Stanisław Ulam nazwał ją metodą Monte Carlo na pamiątkę swojego stryja, który przepuścił przed wojną rodzinną fortunę w tamtejszym kasynie.

Czasami losowanie rozwiązania i sprawdzanie, czy pasuje, jest szybsze od rozwiązywania na piechotę. Algorytm, w którym takie sprawdzanie zależy wielomianowo od wielkości danych, nazywamy NP.

Każdy algorytm P jest z definicji NP. Ale jak jest w drugą stronę? Czy każdy NP jest P?

Proszę na mnie nie patrzeć. Nie mam zielonego pojęcia. Gdybym to wiedział, nie pisałbym artykułów do gazety, tylko opływałbym Karaiby jachtem zakupionym za milion dolarów.

Bo to jest właśnie cały przepis na milion: wystarczy udowodnić, że NP jest P (albo że nie jest, jak podejrzewają matematycy - ale tego też na razie nikt nie udowodnił).

Amerykański biznesmen Landon Clay ufundował siedem nagród po milion dolarów każda za rozwiązanie siedmiu zagadek matematycznych. Ogłosił to w roku 2000, dlatego te zagadki potocznie nazywa się "problemami milenijnymi".

Sześć nagród czeka na wzięcie, wśród nich właśnie problem, "czy NP jest P". Jeden z problemów - tzw. hipotezę Poincarégo - już rozwiązano, ale rosyjski matematyk Grigorij Perelman nie przyjął nagrody (matematycy to dziwni ludzie!).

Od zera do googola. Bestiarium matematyczne.

Pięć diademów, dwa naszyjniki

Tak naprawdę jednak "pytanie NP=P?" jest warte więcej niż milion i być może, jeśli ktoś z państwa znajdzie odpowiedź, warto będzie ją zachować w tajemnicy. Rzecz w tym, że jeśli istnieje jakiś sposób na przejście z NP do P, to znaczy, że niepotrzebnie męczymy się bardzo złożonymi algorytmami, podczas gdy istnieje jakaś cudowna droga na skróty.

I to nie musi być dobra wiadomość. Gdy słyszymy o jakimś szyfrze, że jest niemożliwy do przełamania, to w praktyce oznacza, że złożoność przełamania przez próbowanie wszystkich opcji po kolei (tzw. brute force) rośnie wykładniczo.

Zależność wykładnicza to beznadziejny przypadek. Funkcja wykładnicza rośnie bardzo szybko z tego samego powodu, dla którego logarytmiczna rośnie bardzo wolno - to tak naprawdę ta sama krzywa, tylko zamieniamy miejscami y i x.

Czasem jednak nie ma innego wyjścia. Weźmy prosty, zdawałoby się, problem - znany jako "problem plecaka".

Złodziej włamał się do sklepu jubilerskiego. Widzi diademy za 100 tysięcy, naszyjniki za 20 tysięcy, broszki za tysiąc i tak dalej. I ma tylko jeden plecak, do którego wszystko mu się nie zmieści.

Jak spakować ten plecak, żeby wynieść jak największą fortunę? Rozwiązanie problemu metodą brute force, czyli "próba pierwsza: pięć diademów, dwa naszyjniki i trzy brosze" (a potem próba druga, setna, tysięczna...) ma czas rozwiązania zależny wykładniczo od bogactwa oferty sklepu jubilerskiego.

To znaczy, że złodziej chcący odnaleźć optymalne upakowanie plecaka, będzie tam siedział, aż przyjdzie policja. A jak po niego nie przyjdzie, to złodziej umrze z głodu, bo funkcja wykładnicza rośnie tak szybko, że w przeciętnym sklepie jubilerskim czas szukania odpowiedzi poleci nam w tysiąclecia.

W praktyce raczej zastosuje wybór losowy. Pośpiesznie wrzuci do plecaka, co popadnie, a potem dopiero sprawdzi wartość łupu. Sprawdzanie wartości łupu też rośnie razem z rozmiarami katalogu sklepu jubilerskiego, ale już liniowo. Czyli jest to zagadnienie NP.

Przykład ze złodziejem jest oczywiście żartobliwy, ale z "zagadnieniem plecaka" naprawdę stykamy się w logistyce ("jak optymalnie zaplanować ładunki na frachtowcu"), a nawet w życiu codziennym. Twarde dyski działają dziś szybciej niż kiedyś, bo nie rozrzucają już danych, gdzie popadnie, tylko starają się je optymalnie poukładać.

Jeśli więc ktoś udowodni, że NP=P, wiele programów - od programów zarządzania flotą do systemów operacyjnych - trzeba będzie napisać od nowa. Ale to i tak najmniejszy problem.

Pisaliśmy już o nieprzełamywalnych szyfrach. Szyfry przeważnie są algorytmami typu NP, inaczej byłyby niepraktyczne - w końcu szyfrem chcemy utrudnić życie temu, kto go przełamuje, a nie temu, kto zna poprawny klucz czy hasło.

Zwykle zależność jest wielomianowa dla kogoś, kto zna klucz (albo go poprawnie odgadł), a wykładnicza dla kogoś, kto chce przełamać szyfr metodą brute force. Popularne w informatyce algorytmy szyfrujące używają jako kluczy liczb binarnych, które mogą mieć różną długość - na przykład 128 albo 256 bitów.

Ten drugi jest dwa razy dłuższy od tego pierwszego. To znaczy, że komuś, kto zna (albo odgadł) klucz, odszyfrowanie zajmie dwa razy więcej czasu. Na przykład będą to dwie setne sekundy zamiast jednej setnej. W praktyce tego się nie zauważa (a za rok i tak będą dwa razy szybsze komputery).

Ale przełamywanie tego szyfru metodą brute force będzie już trwało nie dwa razy dłużej, tylko dwa do 128. potęgi razy dłużej, bo tak działa funkcja wykładnicza. Czyli jeśli przełamanie klucza 128-bitowego zajęłoby godzinę, to przełamanie klucza 256-bitowego zajmie 2128 = 340 miliardów miliardów miliardów miliardów godzin, czyli 390 tysięcy miliardów miliardów miliardów lat.

Przypomnę, że Wszechświat ma zaledwie 14 miliardów lat. To znaczy, że nie tylko dwa razy szybszy komputer, ale nawet miliard miliardów razy szybszy komputer nie pozwoli już na przełamanie tego samego szyfru, ale z kluczem 256-bitowym. Wszechświat przestanie istnieć, nim komputer przestanie liczyć.

Bezpieczeństwo szyfrów zależy od pewności, że te algorytmy są NP, ale w żadnym wypadku nie P. Jeśli ktoś udowodni, że NP=P, prawdopodobnie pozna też magiczną drogę na skróty, pozwalającą przełamać większość używanych w praktyce szyfrów. Taki ktoś będzie miał los świata w swoich rękach!

Wyobrażacie sobie, co może zrobić ktoś, kto może się włamać do wszystkich banków, kont pocztowych i silosów atomowych na dobitkę? Albo jeszcze lepiej: co temu komuś zrobi mafia, Al-Kaida i wszystkie trzyliterowe mroczne służby, żeby mieć ten sekret na wyłączność?

To już chyba lepiej byłoby się pochwalić średniowiecznemu inkwizytorowi znajomością pism al-Chuwarizmiego...

Kliknij, żeby powiększyć