Jedna równość za milion dolarów
Wcześniejsze wprowadzenie było nam niezbędne do tego, abyśmy mogli w końcu zacząć mówić o pieniądzach. I to nie byle jakich, bo o równym milionie dolarów.
24 maja 2000 roku Instytut Matematyczny Claya ogłosił listę siedmiu zagadnień matematycznych, za których rozwiązanie wyznaczono nagrody gotówkowe o wartości miliona dolarów. Zagadnienia te nazywamy milenijnymi, choć najnowsze z nich powstało w 1971 roku. To właśnie ono jest przedmiotem naszych rozważań, a przyjmuje postać pytania: czy $P=NP$? Często jednak określa się go po prostu mianem problemu $P=NP$ lub $P$ vs. $NP$.
Pytanie to samo w sobie nie jest łatwe, wymaga więc pewnych wyjaśnień. Problemy decyzyjne możemy podzielić ze względu na ich własności związane ze złożonością obliczeniową:
- jeśli da się skonstruować algorytm wielomianowy, który rozwiązuje dany problem, to problem ten należy do zbioru (klasy) $P$ problemów,jeśli da się skonstruować algorytm, który w wielomianowej liczbie operacji potrafi potwierdzić, że na postawione pytanie odpowiedź brzmi tak,
- jeśli otrzyma dodatkowo rozwiązanie, dla którego tak właśnie jest (świadka), to problem taki należy do zbioru (klasy) $NP$.
Przykład. Rozważmy problem plecakowy. Mamy plecak o pojemności $B$ i zbiór $N$ przedmiotów $X = \left\lbrace x_1, x_2, \dots, x_N\right\rbrace$, każdy z nich o określonej objętości ($w_j$) oraz wartości ($c_j$). Pytanie brzmi: czy istnieje taki podzbiór $X’ \subseteq X$ przedmiotów, że ich łączna objętość jest mniejsza niż $B$, a ich łączna wartość przekracza wskazaną wartość $C$? Inaczej możemy spytać, czy istnieje taki podzbiór $X’ \subseteq X$, że $$\sum_{X’}c_j > C \quad \text{oraz} \quad \sum_{X’}w_j < B.$$ Nie ulega wątpliwości, że jeśli wskażemy podzbiór $X’$, który spełnia wszystkie założenia, to będziemy w stanie to potwierdzić w wielomianowym czasie, dodając odpowiednie wartości i porównując sumy z wartościami granicznymi. Zatem problem plecakowy należy do klasy $NP$ problemów decyzyjnych. Do dziś jednak nie wiadomo, czy należy do klasy $P$.
Łatwo pokazać (no, może nie tak łatwo, ale jednak jest to możliwe), że każdy problem z klasy $P$ należy też do klasy $NP$. To oznacza, że $P \subseteq NP$. Aby zdobyć milion dolarów, wystarczy pokazać, że jest lub nie jest odwrotnie, to znaczy, że $NP \subseteq P$ lub nie.
Istnieje pewien specjalny podzbiór problemów z klasy $NP$. Problemy te nazywamy $NP$-zupełnymi (określenie zupełny zostało zaczerpnięte z logiki) i mają one pewną bardzo ciekawą własność: jeśli uda się stworzyć wielomianowy algorytm rozwiązujący którykolwiek z problemów $NP$-zupełnych, to będzie oznaczać, że każdy problem z klasy $NP$ da się rozwiązać w wielomianowym czasie i w konsekwencji, że $P=NP$.
Na stronie internetowej http://www.win.tue.nl/~gwoegi/P-versus-NP.htm zebrane są artykuły naukowe, których autorzy utrzymywali, że udało im się rozwiązać problem $P=NP$. Wszystko wskazuje jednak na to, że żaden z dowodów nie był poprawny. Zaskakujące jest to, że liczba prac, które miałyby potwierdzać, że $P=NP$ jest bardzo zbliżona do liczby tych, które miałyby pokazywać coś zupełnie odwrotnego.
Źródło: http://xkcd.com.
Wiele osób zaangażowanych w badania związane ze złożonością obliczeniową zakłada, że mimo wszystko $P\neq NP$ i na tym założeniu opiera mniejszą lub większą część swoich wyników. Dopóki jednak nie dowiemy się, jak jest naprawdę, nie możemy być pewni niczego. Gdyby rzeczywistość była taka, że każdy problem z klasy $NP$ da się rozwiązać w wielomianowym czasie, światowe bezpieczeństwo runęłoby bardzo szybko. Okazałoby się bowiem, że większość szyfrowanych danych przesyłanych w internecie da się bardzo szybko odszyfrować nawet bez znajomości jakiegokolwiek klucza. I, co gorsza, oznaczałoby to, że bohater powyższego komiksu musiałby zmienić swoje hobby.