Milion to za mało

Rozwiązania jednego z problemów matematycznych chyba nie doceniono

KIEDY W ROKU 2000 Instytut Matematyczny Claya wyznaczył nagrody wartości miliona dolarów za rozwiązanie każdego z siedmiu tzw. Problemów Milenijnych, znacznie zaniżył wycenę jednego z nich. Gdyby matematycy rozwiązali we właściwy sposób problem informatyczny „P versus NP”, rozwiązanie byłoby warte znacznie więcej niż milion dolarów. Umożliwiłoby bowiem złamanie większości systemów zabezpieczeń w Internecie, zrewolucjonizowałoby naukę, a nawet doprowadziło do rozwiązania sześciu pozostałych Problemów Milenijnych. Trudno zatem przecenić wartość tego najważniejszego z nierozwiązanych problemów w informatyce.

Problem P versus NP dotyczy pozornej asymetrii pomiędzy znajdowaniem rozwiązań a ich weryfikacją. Wyobraźmy sobie na przykład, że planujemy światową trasę spotkań promujących nową książkę. Korzystając z Priceline’u, zaczynasz testować trasy, ale koszty każdej, którą sprawdzasz, przekraczają budżet przeznaczony na podróże. Niestety, wraz ze wzrostem liczby miast, które chciałbyś odwiedzić, liczba możliwych tras do sprawdzenia wykładniczo rośnie, co sprawia, że nawet komputery nie są w stanie wszystkich przetestować. Kiedy jednak przekażesz sprawę swojemu agentowi, ten poda sekwencję lotów. Możesz wtedy łatwo sprawdzić, czy trasa obejmuje wszystkie zaplanowane miasta i czy jej koszt mieści się w zaplanowanym budżecie. Zwróćmy uwagę na asymetrię: znalezienie rozwiązania, czyli zaplanowanie odpowiedniej trasy, jest trudne, ale jego weryfikacja łatwa.

Problem P versus NP dotyczy tego, czy ta asymetria jest rzeczywista, czy pozorna. Inaczej mówiąc: czy fakt, że potrafimy skutecznie sprawdzić rozwiązanie problemu oznacza, że potrafimy także sprawnie znaleźć jego rozwiązanie? Wydaje się oczywiste, że znalezienie rozwiązania powinno być trudniejsze niż jego weryfikacja, ale zdarzały się zaskakujące przypadki: problemy były równie trudne, jak powyższy, ale po głębszej analizie znajdowano sposób, jak się z nimi uporać, podczas gdy w innych sytuacjach trafiano na mur nie do przebicia. Być może jakieś sprytne skrótowe podejście pozwoliłoby ominąć konieczność przeszukiwania milionów potencjalnych tras w problemie promocji książki. Na przykład, jeśli chcielibyśmy znaleźć sekwencję lotów między dwoma odległymi miastami w ramach określonego budżetu, zapewne też załamalibyśmy ręce wobec konieczności sprawdzenia wielkiej liczby możliwych połączeń. Tymczasem struktura tego problemu umożliwiła informatykom opracowanie szybkiej procedury (algorytmu) z pominięciem konieczności mozolnego wyszukiwania.

Problem P versus NP pojawia się w świecie obliczeń wszędzie i sięga daleko poza specyfikę naszego scenariusza podróży – stał się wręcz symbolicznym obliczeniowym Świętym Graalem. Każda próba znalezienia jego rozwiązania tylko coraz mocniej uwidacznia, jak bardzo jest to trudne.

Poddziedzina informatyki teoretycznej zwana teorią złożoności obliczeniowej dotyczy głównie określania stopnia trudności rozwiązywania różnych problemów przez komputery. Litera „P” oznacza klasę problemów, które mogą być skutecznie rozwiązane, jak na przykład sortowanie kolumny liczb w arkuszu kalkulacyjnym lub znajdowanie najkrótszej drogi między dwoma punktami na mapie. Natomiast „NP” – klasę problemów, których rozwiązania komputery mogą zweryfikować. Nasz książkowy problem, zwany w matematyce Problemem Komiwojażera, należy do klasy NP, ponieważ mamy skuteczną

procedurę sprawdzenia, czy rozwiązanie pasuje.

Zauważmy, że NP właściwie obejmuje P jako podzbiór, ponieważ bezpośrednie rozwiązanie problemu jest jednym ze sposobów jego sprawdzenia. Na przykład, odpowiedzią na pytanie: „czy 27 × 89 = 2403?” jest rozwiązanie działania i porównanie zgodności iloczynów. Relację między P i NP przedstawiamy zwykle za pomocą prostego diagramu Venna:

Obszar wewnątrz NP, ale nie wewnątrz P, obejmuje problemy, których nie można rozwiązać żadnym znanym, dostatecznie wydajnym algorytmem („wydajność” oznacza ilość pracy wykonanej w jednostce czasu). Nie wiemy jednak, czy dzieje się tak dlatego, że takie algorytmy nie istnieją, czy po prostu nie jesteśmy na tyle pomysłowi, aby je znaleźć. Takie ujęcie umożliwia inny sposób sformułowania problemu P versus NP: czy te klasy rzeczywiście są różne? A może diagram Venna składa się z jednego koła? Czy wszystkie problemy NP można skutecznie rozwiązać?

Oto kilka przykładów problemów w NP, o których obecnie nie wiadomo, czy należą do P:

Czy w danej sieci społecznościowej istnieje grupa o określonej liczebności, której wszyscy członkowie są przyjaciółmi?

Czy zbiór rozmaitych pudeł do wysyłki zmieści się w określonej liczbie ciężarówek?

Czy uogólnione sudoku (dowolnie duży diagram n × n) ma rozwiązanie? Czy na danej mapie kraje można pokolorować tylko trzema barwami tak, aby żadne dwa sąsiednie nie były w tym samym kolorze?

Tysiące najtrudniejszych problemów NP w różnych dziedzinach, kuszących ich potencjalnych pogromców perspektywą sławy i fortuny, pozostaje nierozwiązanych.

Warto się zastanowić nad sposobem weryfikacji niektórych z tych problemów, a potem nad sposobami ich rozwiązania. Trzeba jednak pamiętać, że rozwiązanie przybliżone lub w małym zakresie (większość z nas potrafi rozwiązać sudoku 9 × 9) nie wystarczy. Aby uznać problem za rozwiązany, algorytm musi znajdować dokładne rozwiązania we wszystkich przypadkach, łącznie z obejmującymi bardzo duży zakres.

Teoretycznie każdy problem da się rozwiązać metodą siłową (brute-force). Można na przykład kolorować mapę na wszystkie możliwe sposoby, szukając tego właściwego, ale liczba takich prób rośnie wykładniczo wraz z liczbą krajów, czyli zakresem albo rozmiarami problemu. Jeśli więc rozmiary te oznaczymy literą n (liczba krajów na mapie lub liczba pudeł do zapakowania na ciężarówki), to do sprawdzenia będzie około 2n możliwości. Niestety, nawet najpotężniejsze superkomputery na świecie nie mają szans w starciu ze wzrostem wykładniczym. Jeśli n=300, co według współczesnych standardów stanowi niewielki rozmiar danych wejściowych, to 2300 przekracza liczbę atomów w obserwowalnym Wszechświecie. Po naciśnięciu przycisku „start” algorytmu z n=300 komputer wyświetli wiatraczek, który będzie wirował dłużej, niż będziemy żyli my i nasi potomkowie.

Na naszej liście są tysiące podobnych problemów z najrozmaitszych dziedzin – od biologii komórki po teorię gier. Problem P versus NP sięga najdalszych zakątków nauki i przemysłu. Gdyby P = NP (diagram Venna byłby jednolitym kołem) i pojawiłyby się szybkie algorytmy dla trudnych problemów, wówczas całej gospodarce cyfrowej groziłaby zapaść. A to dlatego, że w tej dziedzinie znaczna część kryptografii zabezpieczającej – na przykład numer karty kredytowej i hasło – oparta jest na ich „ukryciu” za problemami trudnymi obliczeniowo, które można łatwo rozwiązać tylko wtedy, gdy zna się klucz. Nasze bezpieczeństwo online oparte jest więc na niepotwierdzonych założeniach matematycznych, które okazałyby się błędne, gdyby P = NP.

Co zaskakujące, nawet całą matematykę możemy uznać za problem NP, ponieważ potrafimy zaprogramować komputery tak, aby skutecznie weryfikowały dowody. Faktycznie, wybitny matematyk Kurt Gödel w 1956 roku po raz pierwszy przedstawił problem P versus NP w liście do Johna von Neumanna, pisząc, że równość P = NP „miałaby doniosłe konsekwencje, oznaczałaby bowiem, że [...] pracę umysłową matematyka nad pytaniami typu »tak czy nie?« mogłaby całkowicie zastąpić maszyna”.

Jeśli jesteś matematykiem i martwisz się o swoją pracę, powinieneś wiedzieć, iż gros ekspertów uważa, że P nie równa się NP. Pomijając intuicję, że znalezienie rozwiązania powinno być trudniejsze niż jego sprawdzenie, tysiące najtrudniejszych problemów NP w różnych dziedzinach, o których nie wiadomo, czy należą do P, pozostają nierozwiązane, kusząc ich potencjalnych pogromców sławą i fortuną. Mimo to nikomu nie udało się ani jednego z nich pokonać, czyli napisać skutecznego algorytmu.

Oczywiście, przeczucia i brak kontrprzykładów nie stanowią dowodu. Aby udowodnić, że P nie równa się NP, trzeba w jakiś sposób wykluczyć wszystkie potencjalne algorytmy dla wszystkich najtrudniejszych problemów NP, co wydaje się przekraczać możliwości obecnych technik obliczeniowych. Wprawdzie częściowo sobie z tym poradzono, formułując tzw. twierdzenia barierowe, które wykluczają możliwość stosowania niektórych kuszących strategii dowodowych. W efekcie nie tylko nie znamy ostatecznego dowodu, ale nawet nie mamy pojęcia, jak mógłby on wyglądać. ■