O klasie P wiadomo dość dużo: np. jest zamknięta na składanie i uzupełnienie. Stosunkowo niewiele wiadomo o klasie NP, poza wieloma przykładami problemów do niej należących. Co więcej nie wiemy nawet, czy są problemy, które należą do NP i równocześnie nie należą do P. Problem, czy P = NP, został postawiony w 1971 roku i do dziś pozostaje otwarty. Większość teoretyków informatyki uważa, że P ¹ NP. Wydaje się, że łatwiej jest sprawdzić, że dane rozwiązanie jest poprawne, niż je znaleźć, ale taki argument nie stanowi dowodu.

Istotnym argumentem na rzecz nierówności P ¹ NP jest istnienie klasy NPC, tzw. problemów NP-zupełnych. Klasa NPC ma ciekawą własność, gdyby ktoś znalazł wielomianowe rozwiązanie jakiegokolwiek z problemów należących do tej klasy, to byłby również wielomianowy algorytm dla wszystkich innych problemów z klasy NP. Inaczej, gdyby udowodniono wykładnicze dolne ograniczenie dla jakiegokolwiek problemu z klasy NPC, to wynikałoby stąd, że żadnego z problemów NPC nie można rozwiązać w czasie wielomianowym. Jednym słowem, losy wszystkich problemów należących do klasy NPC są takie same: albo wszystkie mają wielomianowe algorytmy, albo żaden z nich.

Znanych jest ok. 1000 problemów NP-zupełnych. Do takich problemów należą wszystkie wymienione w poprzednim punkcie: problem układanki, problem spełniania, problem kolorowania grafu, problem komiwojażera, problem cyklu Hamiltona. Na przykładzie tych dwóch ostatnich problemów pokażemy na czym polega wielomianowa sprowadzalność jednego problemu klasy NPC do innego problemu tej klasy.

Niech G = <V,E> będzie danym spójnym grafem do problemu cyklu Hamiltona. Skonstruujemy graf G' = <V', E', c> dla problemu komiwojażera przyjmując V' = V, E' = {(i,j) : i, j Î V}, oraz c(i,j) = 0, gdy (i,j) Î E, c(i,j) = 1, gdy (i,j) Ï E. Graf G' jest więc grafem pełnym, a koszt dowolnej krawędzi, która należała do oryginalnego grafu G wynosi 0.

Jeżeli graf G ma cykl Hamiltona H, to jest to też cykl w grafie G', ale suma kosztów krawędzi tego cyklu wynosi zero. Zatem H jest drogą komiwojażera o minimalnym koszcie w grafie G'. Odwrotnie, jeśli w grafie G' istnieje droga komiwojażera o koszcie 0, to wszystkie krawędzie tej drogi musiały występować w grafie G, a więc tworzą one w grafie G cykl Hamiltona. Wynika stąd, że G ma cykl Hamiltona wtedy i tylko wtedy, gdy G' ma drogę komiwojażera o koszcie zero.

Zatem, aby odpowiedzieć na pytanie, czy w danym grafie spójnym istnieje cykl Hamiltona, wykonujemy następujące kroki:

Przekształcenie grafu G w graf G' ma koszt kwadratowy ze względu na liczbę wierzchołków grafu. Gdybyśmy więc umieli wielomianowo rozwiązywać problem komiwojażera, to koszt powyższego postępowania byłby wielomianow i umielibyśmy rozwiązać problem cyklu Hamiltona z kosztem wielomianowym. Zatem problem cyklu Hamiltona został zredukowany do problemu drogi komiwojażera. J

Definicja 3.1 Powiemy, że problem p1 redukuje się w czasie wielomianowym do problemu p2 wtedy i tylko wtedy, gdy

istnieje funkcja f obliczana w czasie wielomianowym, taka że dla dowolnego x, x reprezentuje dane do problemu p1 wttw f(x) reprezentuje dane do problemu p2, oraz
rozwiązaniem problemu p1 dla danych x jest "tak" wttw rozwiązaniem problemu p2 dla danych f(x) jest "tak".

Mając pojęcie redukcji, możemy teraz nieco bardziej dokładnie zdefiniować klasę NPC:

Definicja 3.2 Powiemy, że problem p należy do klasy NPC wttw

p należy do klasy NP oraz
jest NP-trudny, tzn. każdy problem z klasy NP redukuje się do niego w czasie wielomianowym .

Pierwszym problemem, dla którego udowodniono NP-zupełność był problem spełniania formuł rachunku zdań (por. 15.2). Wynik ten, uzyskany w 1971 roku, pochodzi od Cooka i jest uważany za jeden z najważniejszych wyników w informatyce teoretycznej. Większość dowodów NP-zupełności problemów polega na wykazaniu ich redukowalności do problemu spełniania. Nie będziemy w tym wykładzie zajmować się dowodzeniem NP-zupełności problemów, wspomnimy natomiast jeszcze jeden problem, którego NP-zupełność została dowiedziona.

Dany jest zbiór n obiektów o wadze odpowiednio s₁,...,s_n oraz liczba c - maksymalna, dopuszczalna waga obiektów w plecaku. Jaki podzbiór zbioru obiektów wypełni plecak bardziej kompletnie? Dokładniej, szukamy wektora (x_i)_i
£n o elementach 0, 1, dla którego

Wektor (x_i)_i
£n wyznacza w ten sposób, które obiekty umieszczamy w plecaku, a których nie bierzemy. W formie decyzyjnej problem można sformułować jako pytanie: czy istnieje taki ciąg zerojedynkowy (x_i)_i
£n , że

Nie jest znany żaden algorytm wielomianowy rozwiązania tego problemu. Jeśli natomiast mamy dane rozwiązanie, to możemy sprawdzić, czy jest ono poprawne, sumując wagi wybranych obiektów. Udowodniono ponadto, że problem ten jest NP-trudny, dokładniej, udowodniono, że redukuje się on wielomianowo do problemu spełniania. Problem plecakowy jest problemem NP-zupełnym.

Uwaga Wersja problemu plecakowego, w której dla każdego i, mamy nie jeden obiekt, a dowolnie dużo obiektów, oraz c i wagi s_i są liczbami naturalnymi, ma rozwiązanie wielomianowe.

Na zakończenie rozważań o NP-zupełności wspomnijmy, że istnieją problemy, o których nie wiemy, czy należą do klasy NPC. Do takich problemów zalicza się problem badania, czy dana liczba jest pierwsza. Jest to problem decyzyjny, w którym daną jest liczba naturalna, a odpowiedzią jest "tak", tylko wtedy, gdy nie istnieje różna od niej i od zera liczba naturalna, która ją dzieli bez reszty. Łatwo zauważyć, że podobny problem badania, czy dana liczba nie jest pierwsza, należy do problemów NP, bo wystarczy ją podzielić przez wskazany dzielnik. Trudnej jest wykazać, że jest wielomianowe potwierdzenie w przypadku pierwszego, pozytywnego, sformułowania problemu, ale wiadomo, że też należy on do klasy NP. O żadnym z tych dwóch problemów nie wiemy jednak, czy są, czy nie są NP-zupełne.

Pytanie 6: Niech problem polega na zbadaniu, czy dana formuła rachunku zdań jest, czy nie jest tautologią. Czy ten problem jest NP-zupełny?