Gdzie leżą granice obliczalności? Problemy milenijne
Na przełomie wieków, w roku 2000 renomowany Instytut Matematyczny Claya ogłosił listę 7 złożonych problemów matematycznych, które dotąd nie zostały rozwiązane. Każdy z nich wycenił na milion dolarów, czyli mniej więcej tyle, ile wynosiła wysokość Nagrody Nobla. Owe zagadnienia to tak zwane problemy milenijne, ponieważ stanowią one dziedzictwo wieku XX przekazane następnemu pokoleniu. Niestety do dzisiaj został rozwiązany tylko jeden.
Spis treści
Matematyczne problemy milenijne – siła algorytmu
Wśród czysto matematycznych zagadnień znalazło się jedno o fundamentalnym znaczeniu dla informatyki, dotyczące granic praktycznej obliczalności problemów. Wyzwanie to znane jest pod lapidarną i mało mówiącą nazwą „P a NP”, jednak rozwiązanie go byłoby w informatyce przełomem iście kopernikańskim.
Aby zrozumieć kontekst i wagę problemu, trzeba się cofnąć do lat 40. XX wieku. Wtedy to Alan Turing, genialny angielski matematyk, jeden z pogromców Enigmy, prowadził prace nad obliczalnością niektórych problemów, to znaczy możliwością ich rozwiązywania za pomocą komputerów. Zbudował w tym celu formalny model komputera, nazywany odtąd maszyną Turinga, oraz sformalizował pojęcie algorytmu.
Przeczytaj też: Kosmiczna liczba Pi. Jak marcowa solenizantka pomaga nam zdobyć Układ Słoneczny?
Każdy algorytm można zapisać w postaci sekwencji podstawowych kroków. Im więcej tych kroków trzeba wykonać, tym dłużej potrwają obliczenia. Zależy to oczywiście od samego zadania, użytego do jego rozwiązania algorytmu oraz, oczywiście, ilości danych wejściowych.
Zgodnie z intuicją, im więcej danych dostarczamy algorytmowi, tym dłużej komputer będzie go wykonywał. Jednak kluczowe pytanie to nie „czy”, ale „w jaki sposób” ilość danych wpływa na czas obliczeń. Przykład: Czy zwiększenie ilości danych o pewną jednostkę wydłuży czas o kilka sekund (czy nawet dni), czy od razu go… podwoi?
Ta pozornie drobna różnica może mieć olbrzymie znaczenie. Jeżeli dla danych o długości 1 czas obliczeń wynosi zaledwie sekundę, to dla danych o długości 100 – już 2 do potęgi 100, czyli liczbę trzydziestocyfrową, podczas gdy wiek naszego Wszechświata szacuje się na liczbę jedynie osiemnastocyfrową!
I nie pomoże tu użycie szybszego komputera: komputer szybszy miliard razy skreśli z tej liczby zaledwie dziewięć cyfr. A przecież być może już za chwilę będziemy potrzebować dokonywać obliczeń dla liczb o długości 200 i więcej.
Stephen Cook – matematyczne problemy P i NP
Zainspirowany tą obserwacją w 1971 roku amerykański informatyk Stephen Cook wydzielił dwie specyficzne klasy problemów, które dają się rozwiązać za pomocą komputera: P i NP. Klasa P zawiera problemy „łatwe”, czyli takie, dla których istnieje algorytm o rozsądnej relacji między ilością danych a czasem obliczeń. Rozsądnej, czyli takiej, dla której czas obliczeń wraz ze wzrostem ilości danych wydłuża się „o” pewną liczbę jednostek, a nie ulega mnożeniu.
Druga klasa – NP – próbuje spojrzeć z drugiej strony i zawiera takie problemy obliczeniowe, dla których znalezione w jakiś sposób potencjalne rozwiązanie da się zweryfikować (czyli powiedzieć, czy jest prawidłowe) w rozsądnym czasie.
Zatem klasy P i NP nie są rozłączne, bo każdy „łatwy” problem (z klasy P) jednocześnie jest problemem łatwym do sprawdzenia (czyli NP). Problem milenijny dotyczy natomiast pytania odwrotnego: czy każdy problem NP jest jednocześnie problemem P (co oznaczałoby, że P i NP to ten sam zbiór)?
Twierdząca odpowiedź oznaczałaby, że każdy problem NP (w tym również znane klasycznie trudne obliczeniowo problemy) musiałby mieć rozsądny algorytm. Być może w tej chwili go jeszcze nie znamy, ale musi on istnieć. Odpowiedź przecząca stawiałaby granicę obliczalności: pewna grupa problemów na zawsze pozostałaby trudna, bo nawet najszybsze algorytmy i najdoskonalsze komputery nie nadążałyby za potrzebami. Na razie jednak nie umiemy powiedzieć ani „tak”, ani „nie”.
Czy kiedykolwiek uda nam się rozwiązać problem „P a NP”?
Skoro nie można oprzeć się na faktach i dowodach, można posłużyć się sondażem. Opinie naukowców od lat mierzących się z tym problemem skłaniają się ku tezie, że jednak P jest podzbiorem NP, a zatem istnieją trudne problemy, których nigdy szybko nie rozwiążemy.
Takie założenie wykorzystujemy też w praktyce. W wielu przypadkach, na przykład w algorytmach szyfrujących, wykorzystano fakt, że niektóre obliczenia zajmują za dużo czasu, co czyni ich łamanie działaniem nieopłacalnym. I choć jeżeli nagle okazałoby się, że P = NP, to wprawdzie Internet nie zatrzymałby się w miejscu, a bankowość elektroniczna nie uległaby fali rabunków, jednak cień zostałby już na zawsze rzucony.
Być może jednak zamiast mierzyć się z problemem milenijnym wystarczy wymyślić zupełnie inny komputer: nie szybszy, ale działający w sposób nieskończenie równoległy, rozwiązujący problem we wszystkich kierunkach naraz.
Takie nadzieje wiązano m.in. z komputerem kwantowym, ponieważ niektóre obliczenia wykonuje on właśnie w taki sposób. Nadal jednak są takie problemy, z którymi nawet on sobie nie poradzi, a poza tym na przeszkodzie stoi szereg problemów technologicznych. Czy zatem święty Graal informatyki kiedykolwiek zostanie znaleziony?
Bartosz Walter
W pętli czasu, czyli dlaczego czas jest wyzwaniem dla komputerów
Newsletter NTL
Zostaw nam swój adres email i odbierz darmowy rozdział najnowszej książki Tomasza Rożka „Akademia Superbohaterów”
Podcasty NTL
