Tysiąc bardzo trudnych problemów informatycznych to w zasadzie jeden. Tyle że w przebraniu

Na osoby badające te trudne problemy zwane „NP-zupełnymi” czeka nagroda ustanowiona przez organizację non profit Clay Mathematics Institute – milion dolarów za znalezienie szybkiego rozwiązania lub udowodnienie, że rozwiązania nie ma. W latach 70. to wyzwanie stało się bardziej kuszące po wykazaniu, że wszystkie te problemy sprowadzają się właściwie do jednego. Zatem kto poradzi sobie z jednym, ten upora się ze wszystkimi. Ta koncepcja, fundamentalna w informatyce teoretycznej, świadczy o tym, że pewne grupy problemów obliczeniowych tworzą zunifikowaną sieć. Odkrycie szybkiego algorytmu rozwiązującego sudoku dowolnej wielkości będzie równoznaczne z możliwością złamania schematów szyfrowania chroniących naszą gospodarkę cyfrową. Gdy odkryjemy skrót, umożliwiający planowanie podróży w ramach budżetu, będziemy mogli go użyć do rozwiązania niemal każdego otwartego problemu matematycznego.

Znalezienie szybkich algorytmów dla problemów NP-zupełnych (lub udowodnienie, że takie algorytmy nie istnieją) byłoby rozwiązaniem najważniejszej zagadki informatyki – problemu „P versus NP”. P oznacza problemy obliczeniowe, które komputery mogą efektywnie rozwiązać. Zbiór NP zawiera natomiast problemy, których rozwiązania można efektywnie zweryfikować, ale niekoniecznie da się je szybko rozwiązać. NP obejmuje wszystkie P (znalezienie rozwiązania jest równoznaczne z jego weryfikacją), a także trudniejsze problemy, dla których nie znamy efektywnych metod rozwiązywania (możemy je zweryfikować dopiero po rozwiązaniu). Problem „P versus NP” sprowadza się do pytania, czy ta pozorna asymetria między znalezieniem rozwiązania a jego weryfikacją jest rzeczywista, czy iluzoryczna. Być może P=NP i obejmuje ten sam zbiór problemów. Innymi słowy, być może problemy NP, których nie umiemy efektywnie rozwiązywać, wydają się trudne w porównaniu z problemami P, ponieważ wciąż nie wiemy, jak do nich podejść.

Na przykład, czy dysponując określonym budżetem, dowolnie długą listą miast do odwiedzenia i lotów przesiadkowych między nimi (z uwzględnieniem cennika) – da się utworzyć algorytm (zbiór prostych instrukcji), który skutecznie rozstrzygałby o możliwości odwiedzenia wszystkich miast w ramach budżetu? Tego nie wiemy. Znamy nieefektywny algorytm: sprawdź każdą możliwą sekwencję lotów, obejmującą wszystkie miasta, zsumuj koszty podróży i porównaj wynik z budżetem. Jednak wraz ze wzrostem liczby miast liczba tras do sprawdzenia rośnie wykładniczo, aż w końcu zadanie staje się niewykonalne nawet dla najszybszych komputerów. Być może istnieje jakiś sprytny skrót, który ominie wyczerpujące poszukiwania, ale informatycy jeszcze go nie znaleźli. Mając jednak rozwiązanie – w tym przypadku określoną listę lotów – można w rozsądnym czasie sprawdzić, czy trasa obejmuje wszystkie miasta i mieści się w budżecie. Jeśli P=NP, to scenariusz lotów (rodzaj tzw. problemu komiwojażera) zapewne ma szybkie rozwiązanie, ale tego jeszcze nie wiemy.

Oprócz problemu komiwojażera do zbioru NP zalicza się wiele znanych problemów obliczeniowych. Dotyczą one m.in. transportu (np. pakowanie skrzyń do ciężarówek), sieci społecznościowych (ustalanie grup wspólnych znajomych), biologii (określanie sposobów fałdowania białek), a także łamigłówek i gier (np. sudoku, seria Pokémon czy Candy Crush). Można nawet samą matematykę uznać za problem NP, ponieważ jej dowody daje się skutecznie weryfikować. Nazywanie powyższych problemów „trudnymi” może wydać się dziwne, skoro ludzie co dzień sprawnie pakują skrzynie do ciężarówek i rozwiązują sudoku. Algorytm oceniamy jednak jako efektywny tylko wtedy, gdy umożliwia rozwiązanie każdego przypadku – także o bardzo dużym „gabarycie”. Oczywiście komputer szybciej rozwiąże sudoku 9×9 niż milion na milion, więc ścisła definicja „efektywności” odwołuje się do czasu potrzebnego do rozwiązania problemu w zależności od rozmiaru danych wejściowych.

Problem P-versus-NP obejmuje różne problemy obliczeniowe i zależności między nimi, więc można by sądzić, że rozwiązanie wymagałoby zbadania każdego z tych problemów osobno. Załóżmy, że mamy znaleźć efektywny algorytm dla problemu komiwojażera. To byłoby przełomowe odkrycie, ale czy miałoby cokolwiek wspólnego z możliwością rozwiązania wielkich sudoku lub z innymi trudnymi problemami NP? To zaskakujące, ale algorytm obsługujący ten jeden problem całkowicie rozwiązałby problem P-versus-NP.

W 1972 roku informatyk Richard M. Karp opublikował przełomowy artykuł, w którym wykazał, że 21 klasycznych problemów NP ma niezwykłą właściwość: efektywny algorytm rozwiązania dowolnego z nich można wykorzystać nie tylko do rozwiązania pozostałych 20, ale do rozwiązania każdego problemu NP. Nazwał te 21 problemów NP-zupełnymi. W międzyczasie wydłużono listę – odkryto wiele innych problemów NP, które mają tę magiczną właściwość (w tym problem komiwojażera).

Na NP-zupełność można patrzeć z optymizmem lub pesymizmem. Optymizm wiąże się z postrzeganiem fortecy monstrualnie trudnych problemów dzielących nas od potencjalnego skoku technicznego jako domku z kart. Przeniesienie jednego problemu do strefy wykonalności sprawi, że runie cała konstrukcja NP, zaś z gruzów wyłoni się naukowy przełom z efektywnym przemieszczaniem się, szybkim odkrywaniem leków przez fałdowanie białek, a ogólniej z nową erą matematyki. Pesymistyczna hipoteza wiąże się z brakiem wydajnego algorytmu dla jakiegokolwiek z tych trudnych problemów. Skoro optymizm sprowadza się do rozwiązania tylko jednego problemu, to dlaczego jeszcze nikomu to się nie udało? Większość ekspertów skłania się ku opinii, że problemy NP-zupełne nie mają szybkich algorytmów.

Niezależnie od tego, czy szklanka jest do połowy pełna, czy do połowy pusta, koncepcja problemów zupełnych zmieniła sposób, w jaki naukowcy postrzegają obliczenia. Karp udowodnił, że można użyć algorytmu dla jednego problemu NP-zupełnego do rozwiązania innego, wykazując możliwość przetłumaczenia języka jednych problemów na języki innych, pozornie niepowiązanych, dzięki procesowi zwanemu redukcją. Polega to na pokazaniu, jak dowolny przykład jednego problemu można przekształcić w przykład innego. Weźmy problem komiwojażera z listą miast, lotów między nimi i budżetem. Sprowadzenie go do dużego sudoku polega na przyjęciu, że ma ono poprawne rozwiązanie tylko wtedy, gdy możliwe jest odwiedzenie wszystkich miast w ramach budżetu (w przeciwnym razie nie ma poprawnego rozwiązania). W ten sposób po odkryciu efektywnego algorytmu sudoku będzie można go też użyć do problemu komiwojażera, przekształcając przykład w sudoku.

Aby lepiej zrozumieć działanie redukcji, zastosujemy ją do pary innych problemów NP-zupełnych: „problemu trójkolorowania mapy” i „problemu kliki”. Przy trójkolorowaniu chodzi o możliwość takiego oznaczenia trzema kolorami regionów tworzących mapę, aby kolor regionów sąsiadujących nigdzie nie był taki sam. Istotą problemu kliki jest natomiast odpowiedź na pytanie: czy dana sieć społeczna zawiera grupę złożoną z danej liczby osób, które się znają? Oba problemy są NP-zupełne, czyli nie znamy efektywnego algorytmu dla żadnego z nich. Wydaje się też, że oba mają ze sobą niewiele wspólnego. Można jednak przekształcić mapę w sieć społeczną tak, że rozwiązanie jednego problemu umożliwi rozwiązanie drugiego.

W tym celu skorzystamy z mapy Stanów Zjednoczonych. Utworzymy na niej sieć społeczną przypisując każdemu stanowi trzy „osoby”, odpowiadające trzem kolorom: niebieskiemu, zielonemu i czerwonemu. Następnie zapoznamy ze sobą dwie osoby, ale tylko takie, które:

1. nie reprezentują tego samego stanu (np. zielony z Wisconsin nie pozna niebieskiego z Wisconsin);

2. nie są w sąsiednich stanach i w tym samym kolorze (Dakota Północna i Dakota Południowa mają wspólną granicę, więc ich czerwoni przedstawiciele pozostaną obcymi, ale Dakota Północna i Floryda nie graniczą, więc ich czerwoni przedstawiciele się poznają).

Można stwierdzić, że ta sieć społecznościowa licząca 150 osób będzie zawierać klikę 50 wspólnych znajomych tylko wtedy, gdy mapa USA ma poprawne trójkolorowanie. Jeśli znajdziemy 50 wspólnych znajomych w sieci, wszyscy muszą reprezentować różne stany, ponieważ w naszym procesie nie kojarzyliśmy osób, które reprezentowały ten sam stan. Co więcej, kolorowanie odpowiadające klice nigdy nie powoduje, że sąsiednie stany będą miały ten sam kolor, bo zabroniliśmy takich powiązań w sieci. Zatem klika 50 osób odpowiadałaby poprawnemu trójkolorowaniu. Podobnie jeśli w sieci nie ma 50-osobowej kliki, to trójkolorowanie jest wykluczone.

Zredukowanie problemu trójkolorowania mapy do problemu kliki oznacza, że gdyby ktoś odkrył szybki algorytm dla problemu kliki, mógłby go użyć do rozwiązania dowolnego przypadku problemu trójkolorowania mapy. Co istotne, pierwszy krok – przekształcenie mapy w sieć – jest szybki. Lokowanie osób w sieci i tworzenie relacji między nimi nie wymaga żadnych mozolnych poszukiwań ani innych zawiłych procesów obliczeniowych.

Jak wynika z redukcji, nawet jeśli problemy wydają się unikatowe, mogą stać się bardziej uniwersalnymi, niż się wydaje. Sieć redukcji łączy wszystkie problemy NP-zupełne. Rozwiązanie jednego umożliwia uporanie się z dowolnym innym problemem NP.

Możliwość „przekładu” jednego problemu na język innego jest również cechą samych obliczeń, a to rodzi zaskakujące implikacje, jeśli przyjąć, że dowodzenie twierdzenia matematycznego jest równoznaczne z rozwiązywaniem problemu NP-zupełnego. Wybierzmy dowolny nierozwiązany problem matematyczny. Z teorii NP-zupełności wynika, że w grze Candy Crush istnieje pewien poziom, który idealnie koduje ten problem. Jeśli w Candy Crush na tym poziomie efektywny wynik jest osiągalny w konkretnej liczbie ruchów, to początkowy problem matematyczny ma dowód określonej długości; w przeciwnym razie dowodu nie ma. Jednak poradzenie sobie z NP-zupełnością, czyli uporanie się na przykład z fałdowaniem białek, pakowaniem skrzyń lub rozwiązywaniem sudoku, zagroziłoby gospodarce cyfrowej. Byłoby tak, ponieważ szyfrowanie, chroniące nasze dane wrażliwe, działa dzięki stosowaniu problemów obliczeniowych uważanych za nierozwiązywalne.

Warto zauważyć, że chociaż rozwiązanie problemu NP-zupełnego pozwoliłoby złamać szyfr, odwrotna sytuacja nie jest prawdziwa, tzn. nierozwiązywalne problemy leżące u podstaw większości schematów szyfrowania same w sobie nie są NP-zupełne.

Przy tak wielu problemach NP-zupełnych milion dolarów za ich rozwiązanie może wydawać się kuszące i stanowić dodatkową motywację przy planowaniu wakacyjnego wyjazdu lub łamania głowy nad sudoku.