Czym jest Klasa NP (NP)?
Klasa NP obejmuje problemy decyzyjne, dla których poprawną odpowiedź można zweryfikować w czasie wielomianowym względem rozmiaru danych, jeżeli dysponuje się odpowiednim świadectwem – na przykład sugestią rozwiązania lub przyporządkowaniem zmiennych. Formalnie rzecz ujmując, NP zawiera wszystkie języki rozpoznawalne przez niedeterministyczną maszynę Turinga w czasie wielomianowym. W praktyce definicja ta oznacza, że choć znalezienie rozwiązania bywa trudne, jego sprawdzenie pozostaje wykonalne stosunkowo szybko.
Jak dokładnie działa Klasa NP (NP)
Gdy rozpatrujemy problem z NP, myślimy o dwóch etapach. Najpierw algorytm hipotetycznie zgaduje propozycję rozwiązania, co odpowiada części niedeterministycznej. Następnie przechodzi do etapu deterministycznego, w którym weryfikuje poprawność tej propozycji w czasie ograniczonym wielomianem. W modelu teoretycznym proces zgadywania nie kosztuje nas nic, lecz w praktycznych algorytmach równoważna jest mu strategia przeszukiwania przestrzeni rozwiązań, na przykład backtracking lub heurystyczne meta-algorytmy.
Kontekst historyczny i formalne ujęcie
Pojęcie NP ukształtowało się w latach siedemdziesiątych XX w. dzięki pracom Stephena Cooka z University of Toronto oraz Leona Levin’a z Uniwersytetu Moskiewskiego. Cook w 1971 r. opublikował twierdzenie, że problem spełnialności formuł logicznych (SAT) jest NP-zupełny, co oznacza, że każdy inny problem z NP da się do niego sprowadzić w czasie wielomianowym. Tym samym określił fundamenty dla dalszych badań nad złożonością obliczeniową i nadał kierunek analizie granic efektywnego obliczania.
Zastosowania w praktyce
W obszarze algorytmiki statystycznej i uczenia maszynowego liczne zadania sprowadzają się do problemów klasy NP lub NP-zupełnych. Przykładem jest wnioskowanie w sieciach bayesowskich z niepewnymi zmiennymi, planowanie sekwencji działań w systemach automatycznego sterowania czy dopasowanie wzorców w grafach wiedzy. Rozwiązywanie takich zadań często korzysta z aproksymacji, relaksacji lub technik przybliżonego wnioskowania, gdyż bezpośrednie, pełne przeszukanie staje się niepraktyczne przy większych danych.
Zalety i ograniczenia
Największą zaletą problemów z NP jest przewidywalność weryfikacji: gdy algorytm otrzyma propozycję rozwiązania, potrafi szybko potwierdzić jej poprawność, co pozwala projektować protokoły kryptograficzne oparte na nierównej trudności znajdowania i sprawdzania wyników. Ograniczeniem pozostaje brak powszechnie znanych algorytmów wielomianowych dla zadań NP-zupełnych. W konsekwencji inżynierowie sięgają po heurystyki, algorytmy przybliżone lub rozkład zadań na podproblemy, aby uzyskać praktyczne czasy działania.
Na co uważać?
Nadmiernie dosłowne modelowanie rzeczywistych zjawisk jako problemów NP-zupełnych może prowadzić do niepotrzebnych komplikacji implementacyjnych. Zanim zaklasyfikujemy zadanie do NP, warto przeanalizować, czy da się je ograniczyć do podprzypadku z klasy P lub czy dopuszczalna jest aproksymacja. Należy także pamiętać, że oznaczenie „trudny w sensie NP” nie przekłada się automatycznie na nieosiągalność praktycznego rozwiązania; wiele instancji problemów NP-zupełnych rozwiązuje się efektywnie dzięki dopasowanym heurystykom.
Dodatkowe źródła
Dla pogłębienia wiedzy warto zajrzeć do artykułu Stephena Cooka „The Complexity of Theorem-Proving Procedures”, który zapoczątkował badania nad NP-zupełnością. Przystępne wprowadzenie do tematu oferuje rozdział poświęcony złożoności obliczeniowej w podręczniku „Introduction to Algorithms” Cormen-Leiserson-Rivest-Stein. Kompendium definicji i przykładów znajduje się w haśle „Klasa NP” w Wikipedii. Z kolei prace na arXiv dokumentują bieżące badania nad algorytmami przybliżonymi do zadań NP-zupełnych, w tym satysfakcjonującym rozwiązywaniu problemów SAT czy planowania w grafach.
