Algorytmy i złożoność obliczeniowa

Damian Niwiński

Każdy adept matematyki zna momenty olśnienia rozwi _{}azaniem trudnego problemu. Co to jednak znaczy, że problem był trudny? Zapewne nie bez znaczenia jest wiedza adepta: problem trudny dla ucznia, na przykład obliczenie długości elipsy, może nie być takim dla studenta matematyki, który dostrzega go jako przypadek szerszego zagadnienia, dla którego zna metod_{}e rozwi _{}azywania. Podobnie, matematyk uzbrojony w teori_{}e grup (a najlepiej także w komputer) może potraktować jako rutynowe kolorowe zagadki Rubika. Metod_{}e rozwi _{}azywania zagadnień matematycznych, jaka da si_{}e zastosować w wielu (zwykle nieskończenie wielu) przypadkach nazywamy algorytmem. Algorytmy s _{}a być może najbardziej widomym rezultatem działalności matematyków: fizycy, inżynierowie, ekenomiści, oczekuj _{}a od matematyki przede wszystkim metod, które w powtarzalnych sytuacjach pozwol _{}a im obliczać potrzebne wielkości (które, oczywiście, mog _{}a być nie tylko liczbami). Nie trzeba dodawać, że możliwość automatyzacji obliczeń przy pomocy komputera niepomiernie zwi_{}ekszyła zainteresowanie algorytmami.

Czy zawsze, dla sensownie postawionego problemu, można dobrać stosown _{}a metod_{}e algorytmiczn _{}a lub choćby mieć nadziej_{}e, że kiedyś taka metoda zostanie znaleziona? Odpowiedź jest negatywna, co zilustrujemy histori _{}a twz. dziesi _{}atego problemu Hilberta.

W 1900 r., David Hilbert przedstawił Mi_{}edzynarodowemu Kongresowi Matematyków w Paryżu list_{}e 23 najważniejszych zagadnień, jakie, jego zdaniem, wiek dziewi_{}etnasty pozostawił dwudziestemu do rozwi _{}azania. Problem dziesi _{}aty dotyczył znalezienia metody, która dla danego równania Diofantycznego (tj. równania z wieloma niewiadomymi, o współczynnikach wymiernych) rozstrzygałaby, czy istnieje rozwi _{}azanie w liczbach całkowitych. Oczywiście, jeśli takie rozwi _{}azanie istnieje, to zawsze w końcu można je znaleźć metod _{}a kolejnych prób; z drugiej strony dla wielu poszczególnych równań istniej _{}a dowody braku całkowitych rozwi _{}azań. Jednak, jak dowiódł w 1970 r. rosyjski matematyk Jurij Matiasiewicz (wówczas 24–letni), nie istnieje algorytm, który, przyjmuj _{}ac jako dan _{}a równanie Diofantyczne, odpowiadałby w skończonym czasie na interesuj _{}ace nas pytanie. Zauważmy, że już samo sformułowanie tego rezultatu wymagało ścisłego określenia poj_{}ecia algorytmu. Czytelnicy artykułu W. Marka i J. Mycielskiego (Delta 12/1999) pami_{}etaj _{}a, że dokonało si_{}e to w latach trzydziestych naszego wieku za spraw _{}a logików: Gödla, Turinga, Posta i Churcha i Kleene’go; wtedy też opisano pierwsze problemy algorytmicznie nierozstrzygalne, tj. nie rozwi _{}azywalne przez żaden algorytm.

Problemy nierozstrzygalne nie s _{}a jak _{}aś rzadk _{}a anomali _{}a w świecie matematyki; z grubsza mówi _{}ac, nierozstrzygalność pojawia si_{}e zawsze, ilekroć problem jest na tyle ogólny, by można w nim odzwierciedlić – być może poprzez zmyślne zakodowanie – informacj_{}e o wszystkich potencjalnie możliwych algorytmach. Jednak znakomita liczba zagadnień ważnych praktycznie nie jest aż tak ogólna; na przykład w pewnym zastosowaniu możemy potrzebować jedynie równań Diofantycznych o trzech niewiadomych i stopniu co najwyżej pi_{}eć.

O ile algorytm rozwi _{}azuj _{}acy problem istnieje, możliwe jest, jak wiemy, przełożenie go na program komputerowy. Można by wi_{}ec pomyśleć, że granica pomi_{}edzy problemami rozstrzygalnymi a nierozstrzygalnymi jest jednocześnie granic _{}a stosowalności informatyki: każdy problem rozstrzygalny może być w praktyce rozwi _{}azany przez komputer. Tak jednak nie jest. Może sie bowiem okazać, że nasz komputer już dla niewielkich danych potrzebuje takiego czasu (np. setek lat), że oczekiwanie na wynik traci sens. Dzieje si_{}e tak w szczególności, kiedy algorytm wymaga przegl _{}adania wszystkich permutacji, lub choćby wszystkich podzbiorów jakiegoś zbioru. Nie wnikaj _{}ac w natur_{}e elementarnych operacji algorytmu, możemy łatwo obliczyć, że gdyby nawet czas wykonywania takiej operacji był najmniejszym sensownym czasem fizycznym (jeden chronom, 10^{−43} sek.), to wykonanie kolejno 2^{n} takich operacji dla n = 200 przekroczyłoby czas życia człowieka, a dla n = 500 wiek wszechświata. Zapewne niektóre operacje mogłyby być wykonywane jednocześnie na wielu komputerach, tu jednak pr_{}edko napotkamy na nieprzekraczalne ograniczenia przestrzeni, w której takie komputery mogłyby si_{}e pomieścić (nie wspominaj _{}ac o kosztach).

Rozważmy dla przykładu ważne praktycznie zagadnienie znajdowania w grafie tzw. cyklu Hamiltona, tj. p_{}etli, w której każdy wierzchołek wyst_{}epuje dokładnie raz. (Intuicyjnie, jest to najbardziej ekonomiczny sposób obejścia całego grafu.) Oczywista metoda polegałaby na przeszukiwaniu wszystkich możliwych permutacji zbioru wierzchołków grafu. Z matematycznego punktu widzenia jest to niew _{}atpliwie algorytm, jednak jego praktyczna stosowalność ogranicza si_{}e do bardzo małych grafów.

Dla porównania, analogiczne z pozoru pytanie o istnienie tzw. cyklu Eulera, tj. p_{}etli, która dokładnie raz odwiedza każd _{}a kraw_{}edź grafu, posiada dobre rozwi _{}azanie algorytmicznie: Czytelnik słyszał zapewne o twierdzeniu, że cykl Eulera istnieje w grafie wtedy i tylko wtedy, gdy liczba kraw_{}edzi wychodz _{}aca z każdego wierzchołka jest parzysta, ten ostatni warunek można oczywiście sprawdzić w czasie proporcjonalnym do liczby kraw_{}edzi grafu. Wspomniane rozwi _{}azanie wymagało jednak odkrycia eleganckiej własności charakteryzuj _{}acej grafy Eulera. Być może jakaś nieznana własność grafów Hamiltona pozwoliłaby i tutaj na skonstruowanie sprytnego algorytmu, działaj _{}acego, powiedzmy, przynajmniej w czasie O(n^{5}) ? Być może, jednakże, pomimo wysiłków, żadna taka własność nie została dot _{}ad znaleziona. Z drugiej strony, co bardzo intryguj _{}ace, nie znamy również dowodu, który wykluczyłby istnienie algorytmu rozstrzygaj _{}acego interesuj _{}acy nas problem w czasie O(n). Zagadnienie cyklu Hamiltona nie jest odosobnionym przypadkiem; w istocie znane s _{}a dziesi _{}atki matematycznie naturalnych i praktycznie ważnych problemów, których stopień trudności obliczeniowej pozostaje nieznany.

Nie znaczy to, że nigdy nie potrafimy dowieść, że jakiś rozstrzygalny problem jest obliczeniowo trudny. Owszem, dla każdej ,,w miar_{}e porz _{}adnej” funkcji f(n) (np. dla funkcji n^{2}, 2^{n}, n!) potrafimy skonstruować problem nierozwi _{}azywalny przez żaden algorytm w czasie proporcjonalnym do f(n), a zarazem rozwi _{}azywalny przez pewien algorytm pracuj _{}acy w czasie (f(n))^{2}. Jednakże konstrukcja ta, wzorowana na przek _{}atniowej konstrukcji problemu nierozstrzygalnego, jest dosyć sztuczna i rzuca niewiele światła na zagadnienie złożoności ,,prawdziwych” problemów obliczeniowych.

Przedstawiona sytuacja nie powinna nas specjalnie martwić. Jak zwykle w nauce, rzeczywiste trudności s _{}a motorem rozwoju. Współczesne studia nad algorytmami rozwijaj _{}a si_{}e w dwóch kierunkach. Teoria złożoności obliczeniowej próbuje wyjaśniać dlaczego niektóre problemy nie poddaj _{}a si_{}e próbom znalezienia dobrych rozwi _{}azań algorytmicznych. Algorytmika natomiast, inspirowana potrzebami praktycznymi, niestrudzenie poszukuje takich rozwi _{}azań, cz_{}esto na drodze rozszerzenia samego poj_{}ecia algorytmu.

Ujmuj _{}ac rzecz pozytywnie, teoria złożoności d _{}aży do określenia trudności problemów algorytmicznych i klasyfikuje je ze wzgl_{}edu na stopień trudności. Tradycyjnie, problem obliczeniowy uważa si_{}e za praktycznie rozwi _{}azywalny o ile istnieje algorytm, który dla danych rozmiaru n pracuje w czasie proporcjonalnym do n^{k}, dla pewnej stałej k. Problemy o tej własności tworz _{}a klas_{}e zwykle oznaczan _{}a symbolem P (lub PTIME, z ang. polynomial time). Wspomnian _{}a w artykule W. Marka i J. Mycielskiego (Delta 12/1999) klas_{}e NPTIME (lub NP) można określić poprzez rzutowania problemów z P, tj. A ∈ NP o ile A = {x : (∃y) R(x, y) ∧ |y| ≤ |x|^{k}}, gdzie R jest relacj _{}a w klasie P, k jest stał _{}a, a |z| oznacza rozmiar z. Czytelnik może zauważyć, że problem cyklu Hamiltona jest w NP, gdyż relacja ,,permutacja π wierzchołków garfu G jest cyklem Hamiltona w G” jest oczywiście sprawdzalna w czasie wielomianowym.

Świat problemów obliczeniowych ma swoj _{}a struktur_{}e, któr _{}a stopniowo poznajemy. Okazuje si_{}e na przykład, że wiele z pozoru różnych problemów jest w istocie bardzo do siebie podobnych, w tym sensie, że jeden można uznać za tłumaczenie drugiego. Wspomniane wyżej zagadnienie cyklu Hamiltona nie ma na pierwszy rzut oka zwi _{}azku z pytaniem, czy graf można pokolorować trzema kolorami tak, by końce kraw_{}edzi miały różne kolory, a to z kolei z pytaniem, czy dana formuła rachunku zdań jest spełniona przy jakimś wartościowaniu zmiennych. A jednak, istnienie szybkiego (wielomianowego) algorytmu dla któregokolwiek z tych problemów poci _{}agałoby za sob _{}a istnienie analogicznych algorytmów dla pozostałych, a nawet dla wszystkich problemów ze wspomnianej klasy NP. Problemy o tej własności nazywa si_{}e zupełnymi w NP. Poj_{}ecie to zostało sformułowane pod koniec lat sześćdziesi _{}atych przez S.Cooke’a i R.Karpa w USA i niezależnie przez L.Levina w ówczesnym ZSRR.

Badanie stopnia pokrewieństwa pomi_{}edzy problemami i wyróżnianie problemów zupełnych jest jednym z przedmiotów teorii złożoności. Innym ważnym kierunkiem jest porównywanie różnych miar złożoności. Oprócz czasu sensownie jest bowiem badać także rozmiar pami_{}eci operacyjnej komputera potrzebnej do rozwi _{}azania zadania, a także np. liczb_{}e komputerów (lub procesorów), które mogłyby rozwi _{}azać to zadanie pracuj _{}ac równolegle, co może (choć nie zawsze musi) znakomicie przyśpieszyć realizacj_{}e algorytmu. W ostatnich latach, w zwi _{}azku z rozwojem programów interakcyjnych, popularne staje si_{}e modelowanie działania komputera jako gry ze środowiskiem; implikuje to nowe miary złożoności, jak liczba rund lub liczba uczestników gry.

Przejdziemy teraz do algorytmiki, która, b_{}ed _{}ac po cz_{}eści dyscyplin _{}a inżyniersk _{}a, próbuje jakoś radzić sobie z problemami trudnymi obliczeniowo. Jedn _{}a z możliowści jest rozwijanie algorytmów heurystycznych, działaj _{}acych szybko choćby w niektórych przypadkach, a także aproksymacyjnych, tj. poszukuj _{}acych rozwi _{}azań bliskich optymalnym (na przykład, zamiast cyklu Hamiltona, zadowalamy si_{}e ścieżk _{}a odwiedzaj _{}ac _{}a co najmniej 95 % wierzchołków). Nie próbuj _{}ac wyczerpywać ogromnego tematu, wspomnimy tu o kierunkach, które nie rezygnuj _{}a z walki o optymalne rozwi _{}azania.

Jak widzieliśmy na przykładzie problemu grafów Hamiltona, ,,kamieniem filozoficznym” algorytmiki byłby sposób na przeskoczenie konieczności dokonywania wyczerpuj _{}acych przeszukowań wszystkich możliwości. Oto kilka pomysłów, jak można by to uzyskać.

W tak zwanych algorytmach probabilistycznych, przeszukiwanie zostaje zast _{}apione przez losowy wybór. Ide_{}e takiego algorytmu porównać można do sytuacji egzaminu, kiedy student wybiera, powiedzmy, 5 spośród ogłoszonych wcześniej 100 pytań (zamiast odpowiadać na wszystkie 100). Jeśli wszystkie odpowiedzi b_{}ed _{}a dobre, egzamin przyjmuje z dużym stopniem pewności, że student zna cały materiał – pewność ta w istotny sposób opiera si_{}e na fakcie, że student nie mógł przewidzieć wybranych losowo numerów pytań. Przełomowe znaczenie w algorytmice miał zaproponowany w 1976 r. przez M. O. Rabina (korzystaj _{}acy z idei G. Millera) probabilistyczny algorytm rozstrzygaj _{}acy, czy dana liczba n jest pierwsza czy złożona w czasie proporcjonalnym do (log n)^{3}. W teście tym poszukuje si_{}e drog _{}a losowania — nie ewentualnych dzielników liczby n, bo te mog _{}a być rzadkie, ale – subtelnych a zarazem dość licznych ,,świadectw złożoności”. Chodzi tu o liczby x spełniaj _{}ace alternatyw_{}e: x jest nietrywialnym pierwisatkiem z jedności modn lub też x^{n−1} ≢ 1 (mod n) (kiedy n jest liczb _{}a pierwsz _{}a, wiemy z tzw. małego twierdzenia Fermata, że nie ma takich x). Algorytm Millera– Rabina może co prawda z niewielkim prawdopodobieństwem nie wykryć żadnego świadectwa złożoności liczby złożonej i tym samym uznać j _{}a za pierwsz _{}a, mimo to jednak, z uwagi na szybki czas i brak konkurencji, używa si_{}e go w praktyce do generowania wielkich liczb pierwszych, jakie wykorzystywane s _{}a nast_{}epnie w systemie kryptograficznym RSA. Tak wi_{}ec, w algorytmach probabilistycznych poświ_{}ecamy nieco pewności na rzecz szybkości.

Radykalnym rozwini_{}eciem idei algorytmu probabilistycznego jest głośny ostatnio pomysł wykorzystania w obliczeniach efektów kwantowych. Element losowości pojawia si_{}e tu w momencie pomiaru, kiedy to stan kwantowy zostaje zaobserwowany jako klasyczny i informacja zawarta w tym ostatnim uznawana jest za wynik obliczenia. Zanim jednak nast _{}api pomiar, komputer zachowuje si_{}e zgodnie z prawami mechaniki kwantowej. W rezultacie, n rejestrów, które w klasycznym komputerze przyjmować może w danej chwili co najwyżej jeden z 2^{n} możliwych ci _{}agów n bitów w ∈ {0, 1}^{n}, w komputerze kwantowym może w pewnym sensie przyj _{}ać je wszystkie jednocześnie (na przykład, w stanie kwantowym \frac{1}{(\sqrt{2})^{n}} ∑_{w∈\{0,1\}^{n}}[w⟩). Wyczerpuj _{}ace przeszukiwanie może wi_{}ec zostać zast _{}apione wygenerowaniem stanu kwantowego obejmuj _{}acego naraz wszystkie możliwości.

Najbardziej jak dot _{}ad spektakularnym sukcesem w tym kierunku jest zaproponowany przez P. Shora kwantowy algorytm rozkładu liczby całkowitej na czynniki pierwsze. Najlepszy znany ,,klasyczny” algorytm rozwi _{}azuje to zagadnienie w czasie wykładniczym ze wzgl_{}edu na rozmiar przedstawienia binarnego liczby n, choć z drugiej strony, faktoryzacja nie ma charakteru problemu NP–zupełnego. Kwantowy algorytm Shora działa w czasie wielomianowym (dokładnie, C ·(log n)^{2}·(log log n)·(log log log n)). Warto wspomnieć, że możliwość szybkiej faktoryzacji dużych liczb wywołałaby spore zamieszanie, gdyż powszechnie stosowany algorytm szyfrowania RSA opiera si_{}e na hipotezie trudności tego problemu. Trzeba jednak pami_{}etać, że gł_{}eboki matematycznie algorytm Shora istnieje na razie jedynie na papierze, a komputery kwantowe (w odróżnieniu od kwantowej kryptografii) wydaj _{}a si_{}e jeszcze dalekie od fizycznej realizacji.

Fizycznie zrealizowany został natomiast pomysł Adlemana, by do obliczeń wykorzystać reakcje biologiczne, a konkretnie zjawisko ł _{}aczenia si_{}e komplementarnych odcinków DNA w słynn _{}a podwójn _{}a helis_{}e. Jako zadanie obliczeniowe wybrano zanany nam już problem cyklu Hamiltona. W wyniku siedmiodniowego eksperymentu pojawiło si_{}e rozwi _{}azanie. Co prawda testowany graf był niewielki, a wspomniane rozwi _{}azanie jest dostrzegane przez człowieka w ci _{}agu kilkudziesi_{}eciu sekund, jednak zastosowana tu technika może dla dużych grafów okazać si_{}e szybsza niż komputer cyfrowy. Pami_{}etajmy, że możliwość szybkiego rozwi _{}azywania, choćby dziwaczn _{}a technik _{}a, zagadnienia cyklu Hamiltona oznacza szybki algorytm dla dowolnego problemu klasy NP (tłumaczenie takiego problemu na problem cyklu Hamiltona mogłoby odbywać si_{}e przy pomocy komputera tradycyjnego). W odróżnieniu od wyrafinowanego algorytmu Shora, idea testu Adlemana jest prosta. Wierzchołki i kraw_{}edzie badanego grafu reprezentowane s _{}a przez losowo wybrane odcinki DNA w taki sposób, by wskutek komplementarności odpowiednich fragmentów, powstaj _{}ace w wyniku ł _{}aczenia podwójne helisy reprezentowały ścieżki w grafie (nie tylko, oczywiście, ścieżki Hamiltona). Kluczowym momentem jest tu możliwość wygenerowania wszystkich lub niemal wszystkich ścieżek ,,w jednej chwili” (w ci _{}agu kilku sekund); operacja taka jest jak wiemy praktycznie niewykonalna na klasycznym komputerze. Faza eliminacji ,,złych kandydatów”, tak by w końcu pozostało jedynie poprawne rozwi _{}azanie (tj. helisy reprezentuj _{}ace ścieżki Hamiltona) wykorzystywała pomysłowo kilka różnych reakcji biologicznych i to ona była odpowiedzialna za stosunkowo długi czas. Eksperyment Adlemana otwiera now _{}a drog_{}e w informatyce: być może, zamiast konstruować wci _{}aż nowe komputery wystarczy umiej_{}etnie interpretować procesy przetwarzania informacji, jakich pełen jest świat, zwłaszcza świat materii żywej.

Wskazówki do dalszej lektury. Kompendium współczesnej wiedzy o algorytmach, podanej w atrakcyjny i przyst_{}epny sposób znajdzie Czytelnik w dost_{}epnej w polskim przekładzie ksi _{}ażce Th.C. Cormena, Ch.E. Leisersona i R.L. Rivesta Wprowadzenie do algorytmów, WNT 1997. Podstawy teorii złożoności wyłożone s _{}a w klasycznym podr_{}eczniku J.E. Hopcrofta i J.D. Ullmana Wprowadzenie do teorii automatów, j_{}ezyków i obliczeń, PWN, Warszawa 1994. Szerok _{}a perspektyw_{}e problemów i kierunków badawczych tej teorii zakreśla monografia Ch.H. Papadimitriou Computational complexity, Addison–Wesley, 1995. Czytelnik zainteresowany dziesi _{}atym problemem Hilberta może si_{}egn _{}ać po ksi _{}ażk_{}e samego J. Matiasiewicza, Diesiataja problema Gilberta, Nauka Publishers, 1993 (przekład angielski: Yuri V. Matiyasevich, Hilbert’s Tenth Problem, The MIT Press, 1993). Twierdzenie to przedstawione jest także w akademickim podr_{}eczniku Z. Adamowicz i P. Zbierskiego Logika matematyczna. PWN, Warszawa 1991. Eksperyment Adlemana przedstawiony jest przez samego autora w miesi_{}eczniku Świat nauki, nr 10 (86), październik 1998. Wreszcie, ciekawe spojrzenie na granice komputerowej obliczalności przedstawia fizyk R. Penrose w ksi _{}ażkach Nowy umysł cesarza, PWN, Warszawa 1995 i Makroświat, mikroświat i ludzki umysł, Prószyński i S-ka, Warszawa 1997.