Tegoroczna nagroda Gödla powędrowała do Alexandra A. Razborova i Stevena Rudicha za artykuł 'Natural Proofs', opublikowany 10 lat temu w Journal of Computer and System Sciences. Zademonstrowali oni, dlaczego trudne jest udowodnienie, że jakiś problem jest trudny do rozwiązania dla komputera. Czy też zwięźlej - że pewien typ dowodów, zwanych 'dowodami naturalnymi', nie może zostać wykorzystany do separacji klas złożoności obliczeniowej P i NP, przy założeniu, że pewne hipotezy uważane powszechnie za prawdziwe, faktycznie są prawdziwe.
Brzmi to może mało zrozumiale, ale zacznijmy od początku. Kiedy informatyk-praktyk chce rozwiązać jakiś problem przy użyciu komputera, pisze (czy też koduje) program, będący implementacją 'algorytmu' - abstrakcyjnej recepty, pokazującej krok po kroku, co należy robić. Takimi krokami mogą być np. "weź napis i zastąp w nim wszystkie '0' przez '1'", "zwiększ wartość zmiennej X o 1", "sprawdź czy Y jest podzielne przez Z, i jeśli tak, oblicz Y-Z". Choć wymyślenie dobrego algorytmu nie jest trywialnym zdaniem, i wymaga sporej pomysłowości, a czasami i przebłysku geniuszu, same algorytmy wykonywane są 'bezmyślnie'. Można zamknąć w Chińskim Pokoju człowieka z ołówkiem i ryzą papieru, dać mu opis algorytmu Eratostenesa, i nawet jeśli dostał na maturze dwóję z matmy, będzie on w stanie wyprodukować nam śliczną listę liczb pierwszych.
Oczywiście, do wykonywania 'bezmyślnych' zadań świetnie nadają się nie tylko leniwi uczniowie, ale przede wszystkim komputery. Wracamy więc do naszego informatyka-praktyka, który implementację sita Eratostenesa w Javie, C# czy innym języku programowania, ma w małym palcu, i z chęcią napisze program, który rozwiąże nasz problem.
Co do tej chęci, klienci firm informatycznych pewnie w tym miejscu się ze mną nie zgodzą, często bowiem słyszą, że coś jest niewykonalne, albo bardzo trudne w realizacji (i sporo kosztuje). Słowa 'ten problem jest trudny' w ustach informatyka mogą mieć bowiem zupełnie różne znaczenie. Kiedy mówi to programista, może mu chodzić o to, że nie ma pojęcia, jak coś zrobić. Albo może zdaje sobie sprawę, że rozwiązanie problemu może być grą niewartą świeczki (jak np. wdrożenie niepotrzebnej, lecz skomplikowanej funkcjonalności, która pochłonie mnóstwo osobogodzin pracy, a za którą klient nie będzie chciał zapłacić tyle, ile powinien).
Dla informatyka-teoretyka 'trudny' ma jednak zupełnie inne, bardzo konkretne znaczenie, uchwycone w precyzyjnych, formalnych definicjach. Trudność problemu została uzależniona od czasowych i przestrzennych zasobów, potrzebnych do jego rozwiązania. Przykładowo, wyobraźmy sobie, że chcemy odszukać jakieś nazwisko w książce telefonicznej.
Możemy sprawdzić stronę pierwszą, potem drugą, potem trzecią, i tak dalej, aż do zlokalizowania szukanej osoby. Jest to mało efektywna metoda - prawdopodobieństwo tego, że czyjeś nazwisko jest na samym początku książki, jest niewielkie. Co gorsza, im grubsza jest książka telefoniczna, tym więcej czasu stracimy na jej wertowanie - przeciętnie, dwa razy więcej nazwisk oznaczać będzie dwukrotnie dłuższy czas wyszukiwania. Informatycy mówią, że pesymistyczna złożoność obliczeniowa takiego algorytmu wyszukiwania (zwanego liniowym) wynosi O(N), lub też, że jest liniowa. Oznacza to, że liczba kroków algorytmu, jaką musimy wykonać, jest wprost proporcjonalna do 'wielkości' problemu, to znaczy liczby (N) stron albo nazwisk. W najgorszym przypadku musimy przejść przez wszystkie nazwiska, by dotrzeć do ostatniego.
Możemy jednak wymyślić sprytniejszy algorytm, wykorzystując strukturę problemu - to znaczy fakt, że nazwiska ułożone są alfabetycznie. Jeden z nich polegałby na otworzeniu książki w połowie i sprawdzeniu, czy nazwisko mieści się na dwóch stronach, które mamy przed sobą. Jeśli nie, sprawdzamy czy jest wcześniej, czy później, zaznaczamy interesującą nas połówkę, po czym znów dzielimy ją na dwie części. Proces powtarzamy aż do zlokalizowania strony, na której znajduje się szukane nazwisko.
Jak widać, dla grubych książek telefonicznych, ten algorytm jest zdecydowanie wydajniejszy niż poprzedni. Jeśli książka liczy stron 1000, w najgorszym przypadku musielibyśmy wykonać tylko 10 podstawowych, opisanych wyżej kroków, niezależnie od tego, czy szukamy 'Adamskiego', czy też 'Żubra'. Złożoność tego algorytmu jest logarytmiczna - O(log N) - co przy dużych wartościach N robi już ogromną różnicę.
(Logarytm, przypominam, to liczba mówiąca nam, do jakiej potęgi należy podnieść inną liczbę, by uzyskać dany wynik. Ponieważ książkę dzielimy na połówki, interesuje nas logarytm o podstawie 2, a jak łatwo sprawdzić 210 = 1024 > 1000. Lub też inaczej: dzielimy 1000 stron na 500, 500 na 250, 250 na 125, potem musimy kombinować z nierównymi 'połowkami', ale widać już, że zbliżamy się szybko do końca.)
Okazuje się, że można pogrupować problemy według ich złożoności obliczeniowej. Do klasy L należą problemy których czasowa złożoność obliczeniowa jest logarytmiczna - w skrócie, rozwiązywalne w czasie logarytmicznym; do klasy EXP należą problemy rozwiązywalne w czasie wykładniczym, itd. Klasa P (Polynomial) zawiera problemy, dla których zależność ilości kroków algorytmu znajdującego rozwiązanie, od wielkości problemu, jest opisywana jakimś wielomianem.
Na przykład, algorytm mnożenia pisemnego, którego uczyliśmy się w szkole, dla dwóch liczb podobnej długości ma złożoność wielomianową, równą mniej więcej O(N2), gdzie N to ilość cyfr przemnażanych liczb. Łatwo sprawdzić, dlaczego: najpierw przemnażamy wszystkie cyfry pierwszej liczby przez pierwszą cyfrę drugiej, potem wszystkie cyfry pierwszej liczby przez drugą cyfrę drugiej, i tak dalej, jeśli obie liczby mają długość ~N cyfr, musimy wykonać N * N mnożeń. (Pod koniec mamy jeszcze operacje sumowania, ale nie wpłyną one znacząco na złożoność - w dalszym ciągu będziemy mieć wielomian, i to wielomian drugiego stopnia).
Klasa NP (Non-deterministic Polynomial) jest trochę mniej intuicyjnie skonstruowana. Wyobraźmy sobie, że ktoś nam daje potencjalne rozwiązanie jakiegoś problemu. Należałby on do klasy NP, jeśli potrafilibyśmy w czasie wielomianowym sprawdzić, czy rozwiązanie to jest prawidłowe. Przykładowo, jeśli ktoś mówi nam, że 24247 jest dzielnikiem liczby 1918737851, możemy to sprawdzić wykonując po prostu dzielenie, a algorytm dzielenia ma złożoność wielomianową. Natomiast samo znalezienie dzielników liczby 1918737851 do najprostszych nie należy. Najlepszy znany algorytm (klasyczny i deterministyczny, zignorujmy na razie Shora) ma złożoność równą
gdzie b to liczba bitów liczby. Jak widać, jest to złożoność wykładnicza, co tłumaczy, dlaczego problem znajdowania dzielników liczby (faktoryzacja) został wykorzystany w kryptografii z kluczem publicznym. Nie wnikając w szczegóły, złamanie takiego systemu kryptograficznego, jak RSA, wymaga właśnie posiadania szybkiego algorytmu faktoryzacji (albo dużej mocy obliczeniowej).
Faktoryzacja nie jest najbardziej interesującym problemem w NP - chociażby z tego względu, że jest jednym z łatwiejszych (czego dowodem jest fakt, że znamy szybki kwantowy algorytm faktoryzacji). Najtrudniejsze problemy w tej klasie zwane są problemami NP-zupełnymi, które posiadają bardzo ciekawą właściwość - rozwiązanie problemu NP-zupełnego da się efektywnie (tzn. w czasie wielomianowym) przekształcić tak, by stało się rozwiązaniem dowolnego problemu z klasy NP! Problemów NP-zupełnych znamy mnóstwo, dobrze byłoby więc znaleźć szybki algorytm rozwiązujący jeden z nich, albo przynajmniej wiedzieć, że taki algorytm może istnieć.
To właśnie jest wielkie pytanie P?=NP : czy wszystkie problemy z klasy NP dadzą się rozwiązać w czasie wielomianowym (P=NP), czy też może niektóre z nich (np. NP-zupełne) są trudniejsze?
Jako jeden z pierwszych wagę tego pytania dostrzegł sam Kurt Gödel, który w 1956 roku napisał do von Neumanna że gdyby P równało się NP
"miałoby to konsekwencje największej wagi. Pokazywałoby to mianowicie, że pomimo nierozstrzygalności Entscheidungsproblem Hilberta, wysiłek umysłowy matematyków w przypadku pytań na które można odpowiedzieć 'tak/nie' mógłby zostać całkowicie zastąpiony przez maszyny".
Pomimo licznych prób, podejmowanych przez ostatnie 30 lat (problem P?=NP został formalnie sformułowany dopiero w roku 1971 przez Cooke'a), nikomu nie udało się rozstrzygnąć raz na zawsze, czy P równe jest NP. W końcu problem trafił nawet na listę milenijną Claya, co oznacza, że za jego rozwiązanie można więc dostać milion dolarów. Istnieją dobre powody by uważać, że P nie jest równe NP, jednak wszyscy czekają na formalny dowód. Przykład Wielkiego Twierdzenia Fermata pokazuje, że czasami trzeba się po prostu uzbroić w cierpliwość.
Wiemy już, że problem P?=NP jest trudny do rozgryzienia, skoro nikomu to jak dotąd się nie udało. Co ciekawe, wiemy także, mniej więcej, dlaczego jest on trudny!
W 1975 roku Baker, Gill i Solovay udowodnili, że bardzo często stosowna przy dowodzeniu twierdzeń metoda, zwana diagonalizacją, nie może zostać użyta przeciwko P?=NP. Panowie Razborov i Rudich, o których napisałem na samym początku, wytrącili z rąk matematyków kolejną, bardzo obiecującą broń - tzw. dowody naturalne, i za to właśnie dostali nagrodę Gödla.
Co o tym myślą sami zainteresowani? Ankieta Billa Gasarcha, przeprowadzona wśród zajmujących się teorią złożoności obliczeniowych naukowców, pokazuje że są oni mimo wszystko dobrej myśli, i większość z nich uważa, iż rozstrzygnięcie problemu nastąpi przed 2100 rokiem (na korzyść, co nie jest zaskoczeniem, P!=NP). Osobiście jednak uważam, że - jak w tytule wpisu - jesteśmy na to jako Homo Sapiens za głupi, a dowód wyprodukuje jakaś zaawansowana AI.
Komentarze
Pokaż komentarze (9)