Problem P czy NP
Równo sto lat po słynnym programie Hilberta podczas majowej konferencji w Paryżu, Instytut Claya
ogłosił listę siedmiu problemów milenijnych, aby uczcić
nadchodzące nowe tysiąclecie.
Wyboru problemów dokonał Komitet Naukowy, zaś
nagrody finansowe (w wysokości w sumie 7 milionów dolarów) ufundował i zapewnił
Dyrektoriat Instytutu.
Niektóre problemy matematyczne i logiczne da się szybko
rozwiązać przy użyciu komputerów – i stanowią one klasę problemów, z którą
idealny komputer daje sobie radę w czasie będącym wielomianową funkcją zadanych
mu parametrów (należą do tej klasy choćby układy równań liniowych czy problemy
znajdowania najkrótszej drogi). Istnieją jednak zagadnienia, których rozwiązania
znamy, ale nie są to rozwiązania równie „szybkie”, jak w wypadku poprzednim. Czy
da się wszystkie podobne problemy (zgrupowane w pewnej klasie, oznaczonej jako
NP) rozwiązać szybciej? Czy też istnieją takie, których analizy nie da się już
przyspieszyć w żaden sposób? Pytanie ciekawe i szalenie istotne z praktycznego
punktu widzenia, bowiem problemy te związane są z kryptografią (łamaniem kodów),
kolorowaniem map czy układaniem harmonogramów.
Stephen Cook i Leonid Levin sformułowali problem P (tzn.
łatwy do znalezienia) kontra NP (tzn. łatwy do sprawdzenia) niezależnie od
siebie w 1971 roku.
Przykładem problemu NP jest tzw. problem komiwojażera. Jest
to zagadnienie z teorii grafów, polegające na znalezieniu w nim minimalnego
cyklu Hamiltona. Nazwa pochodzi od typowej ilustracji problemu, przedstawiającej
go z punktu widzenia wędrownego sprzedawcy (komiwojażera): dane jest n miast,
które komiwojażer ma odwiedzić, oraz odległość pomiędzy każdą parą miast. Należy
znaleźć najkrótszą trasę wychodzącą z danego miasta, przechodzącą jednokrotnie
przez wszystkie pozostałe miasta i wracającą do tego samego miasta.
Nie są znane algorytmy dające dokładne rozwiązanie tego
problemu w czasie wielomianowym. W praktyce najefektywniejszymi sposobami jego
rozwiązania są algorytmy genetyczne, często wykorzystywane w połączeniu z
heurystycznymi (np. heurystyka najbliższego sąsiada). Są to jednak metody dające
w większości jedynie rozwiązania bliskie optymalnemu. Niekiedy tylko zdarza się,
że otrzymane rozwiązanie jest optymalne. Zależy to głównie od liczby punktów
oraz czasem szczęścia (generacja populacji początkowej, krzyżowanie oraz mutacja
w algorytmach genetycznych zawierają element losowy).
|
