Rozwiązanie może być łatwe do sprawdzenia, choć trudno je znaleźć
W teorii złożoności istnieje ważna asymetria: dla wielu problemów ktoś może podać krótkie „świadectwo” poprawnej odpowiedzi, które da się szybko sprawdzić, mimo że nie znamy równie szybkiego sposobu znalezienia takiego świadectwa od zera. To intuicja stojąca za klasą NP. Przykładowo, jeśli dostaniemy kolejność wierzchołków rzekomo tworzącą ścieżkę Hamiltona, możemy szybko sprawdzić, czy każdy wierzchołek występuje dokładnie raz i czy kolejne są połączone. Znalezienie takiej ścieżki w dowolnym grafie to jednak problem NP-zupełny. Ważne: NP nie oznacza „niewielomianowe” ani „niemożliwe”; chodzi o szybko weryfikowalne odpowiedzi.
Weryfikacja i poszukiwanie to różne zadania
Jeżeli ktoś przekazuje gotowe rozwiązanie, program nie musi już eksplorować całej przestrzeni możliwości. Dostaje wskazówkę, co sprawdzić. W problemie ścieżki Hamiltona takim certyfikatem może być lista wszystkich wierzchołków w proponowanej kolejności. Weryfikator sprawdza długość listy, brak powtórzeń i istnienie odpowiednich krawędzi. Liczba tych operacji rośnie wielomianowo wraz z rozmiarem grafu. To jakościowo inne zadanie niż samodzielne znalezienie kolejności, gdy możliwych permutacji może być ogromnie wiele.
Co naprawdę oznacza NP
Nazwa NP historycznie oznacza nondeterministic polynomial time. Jedna z równoważnych intuicji mówi jednak o problemach decyzyjnych, dla których odpowiedź „tak” posiada certyfikat możliwy do sprawdzenia w czasie wielomianowym. Certyfikat musi mieć także wielomianową długość. Nie każdy problem polega na budowaniu trasy: certyfikatem może być przypisanie wartości logicznych, wybór elementów zbioru, kolorowanie grafu albo inna struktura. Wspólny motyw jest ten sam — jeśli rozwiązanie dostaniemy, możemy efektywnie potwierdzić, że spełnia warunki.
Najczęstsze nieporozumienie
NP bywa rozwijane potocznie jako „non-polynomial”, ale to błędne. Każdy problem z klasy P należy także do NP, bo jeśli potrafimy szybko rozwiązać problem, tym bardziej potrafimy szybko sprawdzić rozwiązanie. Otwarte pytanie brzmi, czy P i NP są w rzeczywistości tą samą klasą. Nie wiemy więc, czy asymetria „łatwo sprawdzić, trudno znaleźć” jest dla najtrudniejszych problemów NP fundamentalna, czy tylko wynika z braku odpowiednio sprytnych algorytmów.
Dlaczego przykład Hamiltona jest tak dobry
Ścieżka Hamiltona pokazuje tę różnicę bez specjalistycznej notacji. Dla n wierzchołków kandydat ma długość proporcjonalną do n, a sprawdzenie jego poprawności jest mechaniczne. Tymczasem problem decyzyjny „czy taka ścieżka istnieje?” jest NP-zupełny. To nie dowodzi, że każdy algorytm musi być wolny — właśnie tego typu twierdzenia są związane z nierozstrzygniętym P kontra NP — ale umieszcza problem w klasie, która skupia najbardziej znane przykłady tej asymetrii.
Praktyczna lekcja
W rzeczywistych systemach ta różnica ma znaczenie wszędzie tam, gdzie łatwo zweryfikować plan, harmonogram albo konfigurację. Możemy mieć szybki moduł sprawdzający poprawność, choć moduł poszukujący dobrego rozwiązania korzysta z heurystyk, solverów, przeszukiwania lub optymalizacji. Teoria złożoności pozwala nazwać tę różnicę i nie mylić „mam szybki tester” z „mam szybki generator rozwiązań”.
Dlaczego certyfikat musi być krótki
W definicji NP samo istnienie jakiegoś dowodu odpowiedzi „tak” nie wystarcza. Certyfikat musi mieć długość ograniczoną wielomianem rozmiaru wejścia, a weryfikator musi działać w czasie wielomianowym. To ważne, bo program nie mógłby szybko sprawdzić świadectwa o astronomicznej długości — samo jego odczytanie zajęłoby zbyt wiele kroków. W przypadku ścieżki Hamiltona certyfikat jest naturalnie krótki: to kolejność n wierzchołków. Dla SAT jest nim przypisanie wartości n zmiennym. Dzięki temu pojęcie „łatwo sprawdzić” pozostaje rzeczywistą własnością algorytmiczną, a nie sztuczką polegającą na ukryciu całej trudnej pracy w gigantycznym załączniku do odpowiedzi.