Problem P = NP: klasy złożoności i NP-zupełność

Teoria złożoności bada zasoby potrzebne do rozwiązywania całych rodzin instancji. Problem decyzyjny opisuje się przez język formalny: do języka należą dokładnie kody wejść, dla których odpowiedź brzmi „tak”. Algorytm rozstrzygający musi zakończyć działanie również na wejściach z odpowiedzią „nie”.

Podstawową zmienną jest długość wejścia, oznaczana przez $n$. Jeżeli liczba jest zapisana binarnie, jej wartość może być wykładniczo większa od długości zapisu. Algorytm wykonujący liczbę operacji proporcjonalną do wartości tej liczby nie musi więc być wielomianowy względem wejścia; takie zależności występują w algorytmach pseudowielomianowych.

Czas wielomianowy oznacza ograniczenie $O(n^k)$ dla stałego wykładnika $k$. Klasa $P$ obejmuje problemy decyzyjne rozwiązywane deterministycznie z takim ograniczeniem w najgorszym przypadku. Standardowe modele deterministyczne symulują się z narzutem wielomianowym, dlatego klasa jest odporna na wiele zmian szczegółów modelu.

W klasie $NP$ kluczowe jest istnienie krótkiego świadectwa pozytywnej odpowiedzi. Dla wejścia $x$ szuka się ciągu $y$ o długości ograniczonej wielomianem w $|x|$. Weryfikator otrzymuje oba ciągi i sprawdza postulowaną własność w czasie wielomianowym. Wejście pozytywne musi mieć przynajmniej jedno poprawne świadectwo, a wejście negatywne nie może mieć żadnego.

Na przykład w problemie kolorowania grafu trzema kolorami świadectwem jest przypisanie koloru każdemu wierzchołkowi. Weryfikator kontroluje, czy końce każdej krawędzi otrzymały różne kolory. Ta kontrola nie dostarcza sama z siebie metody znalezienia kolorowania.

Równoważny opis wykorzystuje niedeterministyczną maszynę Turinga. Maszyna dokonuje wyborów tworzących różne gałęzie obliczenia i akceptuje wtedy, gdy przynajmniej jedna gałąź kończy się akceptacją. Wielomianowo ograniczona jest długość gałęzi, choć całe drzewo może mieć wykładniczo wiele węzłów.

Niedeterminizm nie oznacza losowości, fizycznej równoległości ani obliczeń kwantowych. Skrót NP pochodzi od angielskiego „nondeterministic polynomial time”, a nie od „non-polynomial”. Każdy język z $P$ należy do $NP$, ponieważ jego weryfikator może sam obliczyć odpowiedź i zignorować świadectwo.

Dopełnienie języka zamienia odpowiedzi pozytywne i negatywne w obrębie ustalonego zbioru wszystkich słów. Klasa coNP składa się z języków, których dopełnienia są w $NP$. Dzięki temu negatywne odpowiedzi dla problemu z $coNP$ mają wielomianowo sprawdzalne świadectwa.

Przykładowo problem tautologii pyta, czy formuła boolowska jest prawdziwa przy każdym wartościowaniu. Świadectwem odpowiedzi negatywnej jest jedno wartościowanie, przy którym formuła jest fałszywa. Problem tautologii jest coNP-zupełny przy standardowych redukcjach wielomianowych.

Nie wiadomo, czy $NP=coNP$. Gdyby $P=NP$, równość z $coNP$ również by zachodziła, ponieważ $P$ jest zamknięta na dopełnienie: wystarczy zamienić końcową akceptację z odrzuceniem. Sama hipotetyczna równość $NP=coNP$ nie daje obecnie znanego dowodu $P=NP$.

Faktoryzacja wymaga dodatkowego rozróżnienia: znalezienie czynników jest problemem wyszukiwania, a nie bezpośrednio językiem. Standardowy wariant decyzyjny pyta, czy liczba ma nietrywialny dzielnik nieprzekraczający podanego progu. Należy on do $NP$ i $coNP$; pełny rozkład wraz z efektywnym testem pierwszości pozwala również sprawdzić brak odpowiednio małego dzielnika. Nie znamy dowodu NP-zupełności tego wariantu.

Redukcja wiele-do-jednego przekształca instancję problemu $A$ w instancję problemu $B$ za pomocą funkcji obliczalnej w czasie wielomianowym. Warunkiem jest zachowanie odpowiedzi w obie strony. Rozmiar wyniku jest wielomianowo ograniczony, ponieważ samo zapisanie wyniku wymaga czasu.

Jeżeli umiemy efektywnie rozwiązywać $B$, redukcja pozwala rozwiązywać $A$: najpierw wykonujemy przekształcenie, następnie uruchamiamy algorytm docelowy. Kierunek redukcji opisuje więc kierunek korzystania z algorytmu, a nie potoczne podobieństwo problemów.

Problem NP-trudny przyjmuje redukcje ze wszystkich języków z $NP$. Problem NP-zupełny musi dodatkowo sam należeć do $NP$. Dowodząc NP-zupełności nowego problemu, zwykle wykazuje się:

• wielomianowy rozmiar świadectwa i czas jego sprawdzania;
• konstrukcję redukcji ze znanego problemu NP-zupełnego;
• równoważność odpowiedzi dla instancji źródłowej i docelowej;
• wielomianowy czas i rozmiar konstrukcji.

Twierdzenie Cooka–Levina ustanawia NP-zupełność SAT. Historia niedeterministycznego obliczenia zostaje opisana przez zmienne i lokalne warunki poprawności kolejnych konfiguracji. Powstała formuła jest spełnialna dokładnie wtedy, gdy istnieje poprawna historia zakończona akceptacją.

Pytanie $P=NP$ dotyczy tego, czy wielomianowa weryfikowalność zawsze pociąga za sobą wielomianowe rozstrzyganie. Problem pozostaje otwarty; przekonanie o nierówności tych klas nie zastępuje dowodu. Jest jednym z problemów milenijnych Clay Mathematics Institute.

Algorytm wielomianowy dla jednego problemu NP-zupełnego wystarczyłby do wykazania równości klas. Udowodnienie, że choć jeden język z $NP$ nie należy do $P$, wystarczyłoby do ich rozdzielenia. Niepowodzenie konkretnego algorytmu ani duża liczba przetestowanych instancji nie stanowią takiego dowodu.

Równość klas miałaby konsekwencje dla wyszukiwania świadectw. Można pytać, czy istnieje poprawne świadectwo rozpoczynające się od określonego prefiksu, a potem ustalać jego kolejne bity. Takie pytania nadal należą do $NP$, więc przy $P=NP$ cała procedura byłaby wielomianowa.

Dla wielu problemów optymalizacyjnych wersja decyzyjna pyta o istnienie rozwiązania osiągającego dany próg. Jeżeli wartości celu mają wielomianowo ograniczoną długość zapisu, wyszukiwanie binarne progu i odtwarzanie świadectwa często pozwalają odzyskać optimum. Zależność między decyzją a optymalizacją trzeba jednak wykazać dla konkretnej reprezentacji problemu.

Gdyby $P$ i $NP$ były różne, problemy NP-zupełne nie miałyby deterministycznych algorytmów wielomianowych. Nie oznaczałoby to automatycznie wykładniczego dolnego ograniczenia. Hipoteza ETH stawia silniejsze wymaganie dla 3-SAT: wyklucza czas $2^{o(n)}$, gdzie $n$ oznacza liczbę zmiennych.

Najgorszy przypadek nie opisuje całej praktyki obliczeniowej. Instancje pochodzące z zastosowań mogą mieć strukturę ułatwiającą rozwiązanie. Heurystyki mogą szybko znajdować dobre rozwiązania, ale bez gwarancji czasu lub jakości na wszystkich wejściach.

Ograniczenie problemu może zmienić jego klasę złożoności: 2-SAT należy do $P$, natomiast 3-SAT jest NP-zupełny. Aproksymacja zastępuje optimum rozwiązaniem z określoną gwarancją jakości; algorytmy parametryzowane izolują koszt zależny od wybranego parametru. Algorytm FPT ma czas postaci $f(k) \cdot n^c$, gdzie $c$ jest stałe niezależne od parametru $k$. Nie musi to być czas wielomianowy, gdy parametr rośnie wraz z wejściem.

Funkcje jednokierunkowe mają być łatwe do obliczenia, lecz trudne do odwrócenia na typowych wejściach. Przy $P=NP$ można byłoby wielomianowo wyszukiwać przeciwobrazy, więc takie funkcje w standardowym sensie nie istniałyby. Zagrożone byłyby fundamenty wielu konstrukcji kryptografii obliczeniowej, nie zaś bezwarunkowe bezpieczeństwo informacyjne.

Sama nierówność $P$ i $NP$ nie wystarcza do bezpieczeństwa kryptograficznego. Zapewniałaby trudność pewnych problemów w najgorszym przypadku, podczas gdy atakujący mierzy się z instancjami generowanymi według określonego rozkładu. Potrzebne są dodatkowe założenia o trudności przeciętnego przypadku.