Świat pełen problemów

Wbrew temu, co można wywnioskować patrząc na dzisiejsze zastosowanie komputerów, nie zostały one pierwotnie stworzone do zapewniania rozrywek ich użytkownikom. Komputer (z ang. computer} — maszyna licząca) powstał z myślą o wykonywaniu złożonych obliczeń związanych z poszukiwaniem rozwiązań pewnych ściśle zdefiniowanych problemów.
Te problemy możemy sklasyfikować ze względu na rodzaj rozwiązania, którego oczekujemy. Wyobraźmy sobie, że musimy zmierzyć się z zadaniem rozkładu liczby $k$ na czynniki pierwsze. Taki problem nazywamy problemem funkcyjnym — jego rozwiązaniem jest wartość lub zbiór/ciąg pewnych wartości. Jeśli liczba $k$ jest mała, możemy dość szybko znaleźć rozwiązanie ręcznie. Dla kilkucyfrowej liczby, np. 4790077, musielibyśmy na to poświęcić już co najmniej kilka zimowych wieczorów. Mimo to, nawet przeciętny komputer potrzebuje nie więcej niż pięć tysięcznych sekundy, żeby stwierdzić, że $4790077=2089\cdot 2293$. Z większymi liczbami radzi sobie już jednak gorzej.

Problem rozkładu liczby na czynniki pierwsze jest jednym z najważniejszych problemów współczesnej informatyki teoretycznej. Na założeniu, że dla pewnych (bardzo dużych) liczb pierwszych $p$ i $q$, obliczenie iloczynu $k=pq$ zajmuje komputerowi moment, ale na rozłożenie liczby $k$ na czynniki pierwsze potrzebuje on już kilku lat, opiera się wiele współczesnych algorytmów wykorzystywanych do szyfrowania danych (np. RSA). Czy jednak założenie to może być tak silne, że potrafimy bez mrugnięcia okiem oprzeć na nim tak istotne aspekty naszego życia jak zlecenia przelewów w banku internetowym czy choćby przesyłanie pocztą elektroniczną poufnych danych? I tak, i nie. Okazuje się, że mimo wielu starań nie udało się odnaleźć dotąd sposobu na szybkie rozłożenie dużej liczby na czynniki pierwsze, ale też nie pokazano, że (przy pewnym założeniu) nie da się tego zrobić. Są jednak pewne problemy, o których możemy śmiało powiedzieć, że małe są szanse na to, że da się je rozwiązać szybko. Dlaczego? O tym jest właśnie ten artykuł.

Podstawową grupę problemów rozważanych w świecie informatyki stanowią problemy decyzyjne. Mają one postać pytania, na które odpowiedź brzmi tak lub nie. Gdybyśmy chcieli sformułować problem rozkładu liczby na czynniki pierwsze w postaci decyzyjnej, moglibyśmy zapytać: czy dana liczba $k$ jest pierwsza (lub: czy dana liczba $k$ jest złożona)? Problemy decyzyjne są łatwiejsze w rozważaniach, a~jednak przydatne — jeśli uda się pokazać, że problem decyzyjny jest trudny, to związany z nim problem funkcyjny nie może być łatwiejszy (gdybyśmy umieli rozłożyć liczbę łatwo na czynniki pierwsze, to równie szybko dowiedzielibyśmy się, czy jest pierwsza, czy nie). Wśród innych problemów decyzyjnych moglibyśmy wymienić choćby następujące:

• Czy w danym multizbiorze $A$ liczb wymiernych istnieje podzbiór $A’$ taki, że suma elementów ze zbioru $A’$ jest równa sumie elementów ze zbioru $A-A’$? (problem podziału zbioru)
• Czy w danym multizbiorze $A$ liczb wymiernych istnieje podzbiór $A’$ taki, że suma jego elementów jest równa $b$? (problem sumy podzbioru)
• Czy dane liczby naturalne $n$ i $m$ są względnie pierwsze?

Zauważmy, że każdy z nich ma charakter ogólny. Problemy opisujemy bowiem pewnymi parametrami, które mogą przyjmować dowolne wartości. Jeśli je im przyporządkujemy (pytając np. czy konkretna liczba 4790077 jest pierwsza), to mówimy, że mamy do czynienia z pewną instancją tego problemu.

Jak mierzymy algorytmy?

W poprzednim paragrafie użyliśmy określeń szybko i wolno w kontekście tego, jak komputery radzą sobie z problemami. Ale co to znaczy, że komputer rozwiązuje problem szybko? Gdzie jest granica między szybko a wolno? Czy szybko na jednym komputerze oznacza też szybko na każdym innym? To ciekawe pytania, na które spróbujemy teraz odpowiedzieć.

Komputer jest tylko maszyną — nie jest istotą inteligentną, choć rozwój sztucznej inteligencji mógłby napawać nas strachem. Nie należy jednak brać dosłownie wizji przedstawianych przez pisarzy fantastycznych. Ustalmy więc, że komputer jest maszyną wykonującą jedynie polecenia człowieka. Tę własność wykorzystujemy do rozwiązywania trapiących nas problemów, konstruując algorytmy. Algorytmy rozwiązujące problemy to procedury, które zastosowane do jego dowolnej instancji, wskażą jej rozwiązanie po wykonaniu skończonej liczby kroków. W naszym przypadku rozwiązanie to jest pozytywną lub negatywną odpowiedzią na postawione pytanie.

Algorytmy są różne — rozwiązać dany problem można przecież na wiele sposobów, stosując wiele podejść i różnych metod. Każdy algorytm wymaga jednak wykonania pewnej liczby operacji, zanim się zakończy. W większości przypadków nie liczymy jednak absolutnie wszystkich operacji, a jedynie te, które częstością swojego występowania dominują nad innymi. Te operacje, które bierzemy pod uwagę, nazywamy operacjami elementarnymi. Mimo wszystko, ich liczba zależy jednak od instancji problemu — intuicja podpowiada nam, że odpowiedź na pytanie, czy 817504253 jest liczbą pierwszą wymaga więcej operacji niż odpowiedź na pytanie, czy taką liczbą jest 13. Jak zatem określić, jaka jest szybkość algorytmu, skoro dla każdej instancji wymaga on różnej liczby operacji?

Rozważania dotyczące tych zagadnień rozpoczęły się na dobre w latach sześćdziesiątych dwudziestego wieku, kiedy zaczęto konstruować pierwsze, powolne komputery. Już (a może dopiero) wówczas zauważono, że względnie łatwo jest skonstruować algorytm, który rozwiązuje dany problem decyzyjny, ale wymyślenie takiego, który potrzebuje na to małej liczby operacji może być wyzwaniem. Teoria złożoności obliczeniowej, bo tak nazywa się dziedzina informatyki zajmująca się badaniem czasu działania algorytmów, do dziś dzień opiera się na próbach konstrukcji coraz to szybszych algorytmów.

Jednym z najczęściej spotykanych podejść jest próba określenia górnej granicy liczby operacji, których algorytm potrzebuje do rozwiązania danej instancji problemu, przez rząd funkcji zależnej od długości zakodowanej instancji. Wow, brzmi skomplikowanie, dlatego spójrzmy na przykład:

Przykład. Niech dana będzie liczba $k$. Chcemy sprawdzić, czy jest ona liczbą pierwszą. W tym celu zastosujemy następujący, prymitywny algorytm:

dla i ze zbioru {2, 3, ..., k-1}
    jeśli (k mod i) = 0 wtedy zwróć nie
zwróć tak

Powyższy algorytm wykona, dla dowolnej liczby $k$, co najwyżej $k-2$ operacji dzielenia modulo. Operacje porównania możemy pominąć jako nieistotne. Nasz algorytm wykona zatem co najwyżej $k-2$ operacji. Jeśli jednak weźmiemy pod uwagę, że instancja problemu jest opisana liczbą $k$ zapisaną w systemie binarnym (a zwykle tak zakładamy), to długość tego opisu jest równa $n = \lfloor \log_{2}k\rfloor + 1$, a zatem górną granicę liczby operacji niezbędnych do zakończenia działania algorytmu da się opisać funkcją $f(n) = 2^{n} – 2$, choć nie zawsze ta granica musi być osiągana (Czytelnikowi pozostawiam wykazanie tego faktu).

W praktyce nie interesuje nas jednak, czy liczbę operacji elementarnych zależnych od długości $n$ opisu instancji problemu, da się ograniczyć od góry funkcją $f(n) = 2^n – 2$, czy $f(n) = 3\cdot2^n – 12$. Najistotniejsze z punktu widzenia naszych rozważań jest to, jakiego rzędu jest ta funkcja. Jeśli istnieje taka funkcja $t(n)$, że $\lvert f(n)\rvert \leq c\cdot t(n)$ dla pewnej stałej $c$ i wszystkich $n$ większych od pewnej wartości $n_0$, to mówimy, że funkcja $f(n)$ jest rzędu $t(n)$ i zapisujemy to jako $f(n) = O(t(n))$ (czyt. $f$ jest rzędu duże $o$ od $t(n)$). W rzeczywistości obie wskazane funkcje: $2^n – 2$ oraz $3\cdot2^n – 12$ są rzędu $O(2^n)$. Nie jest zaskoczeniem, że staramy się znaleźć jak najlepsze ograniczenie danej funkcji $f$. Przecież każda funkcja, która jest $O(2^n)$ jest też $O(10^n)$, ale drugie ograniczenie nie jest dla niej zbyt dobre. Pewnym rozwiązaniem tego problemu jest stosowanie notacji $\Theta$, ale dla naszych rozważań nie ma ona istotnych zastosowań. Warto jednak wiedzieć, że istnieje.

Ćwiczenie. Zanim przejdziemy dalej, sprawdź jak sobie radzisz z określaniem rzędu funkcji. W każdym podpunkcie zebrano dwie funkcje, które mają taki sam rząd (w sensie notacji $O$). Jaki on jest? Wskaż najlepszy.

• $f(n) = 14n^3 – 12n^2 + 7n – 3$, $g(n) = n^3+1928n^2$,
• $h(n) = 12n\log n + 13n$, $i(n) = 148n\log n + \log n$,
• $j(n) = 7\cdot 3^n + 12\cdot 2^n + n$, $k(n) = 3^{n+12} + 1$.

Pokaż, że każda funkcja rzędu $O(n^3 + 12n^2)$ jest też rzędu $O(n^3)$.

Jeśli liczba operacji wykonywanych przez algorytm da się ograniczyć z góry przez wielomian, to znaczy jest rzędu $O(p(n))$, gdzie $p(n)$ jest pewnym wielomianem, np. $n^{12}$, $n^7$ itp., to mówimy, że algorytm jest wielomianowy lub że algorytm działa w czasie wielomianowym. W innym przypadku mówimy, że algorytm jest wykładniczy. Ten podział jest bardzo istotny i powszechny — przyjmuje się, że algorytmy wielomianowe są szybkie, a te wykładnicze wolne. Dlaczego? Niech to zaprezentuje poniższa tabela.

Załóżmy, że nasz procesor jest w stanie wykonać miliard operacji elementarnych w ciągu sekundy. W poniższej tabeli zaprezentowano zestawienie, które pokazuje, ile czasu wymagałaby realizacja algorytmów o pewnej określonej od góry liczbie operacji dla instancji wybranej długości:

Porównanie czasu działania algorytmów na procesorze wykonującym miliard operacji elementarnych w ciągu sekundy

Okazuje się więc, że algorytmy wielomianowe istotnie działają o wiele szybciej niż te wykładnicze. Wróćmy na chwilę do problemu weryfikacji pierwszości liczby. Dopiero w 2002 roku trzech hinduskich badaczy — Manindra Agrawal, Neeraj Kayal oraz Nitin Saxena — zaprezentowało algorytm wielomianowy, który to robi. Do tamtego momentu stosowano jedynie algorytmy wykładnicze.

Źródło: http://xkcd.com. Jeśli chcesz się dowiedzieć więcej o problemie, którego dotyczy ten komiks, poszukaj informacji o problemie komiwojażera.

Pytanie, które można zadać brzmi, czy każdy algorytm wielomianowy jest rzeczywiście wielomianowy zawsze? I na odwrót — czy nie jest tak, że na jednej maszynie algorytm będzie wykładniczy, a na drugiej wielomianowy (na przykład gdy zmodyfikujemy zbiór operacji elementarnych)? Okazuje się, że wielomianowość algorytmów zachowuje się przy ich przenoszeniu między maszynami, choć rząd funkcji może się zmienić. Jeśli jednak trzymamy się pewnych reguł gry, nasz algorytm wielomianowy nie stanie się nagle algorytmem wykładniczym.