P kontra NP: pytanie, którego wciąż nie umiemy rozstrzygnąć
P kontra NP pyta w uproszczeniu: jeżeli poprawność rozwiązania można sprawdzić w czasie wielomianowym, czy rozwiązanie można też w takim czasie znaleźć? Klasa P obejmuje problemy rozwiązywalne efektywnie przez deterministyczny algorytm, a NP — problemy z efektywnie weryfikowalnym certyfikatem odpowiedzi „tak”. Wiemy, że P jest zawarte w NP, ale do dziś nie wiadomo, czy P=NP, czy P≠NP. Według Clay Mathematics Institute problem pozostaje nierozwiązany. Gdyby P=NP, wszystkie problemy NP-zupełne miałyby algorytmy wielomianowe; gdyby P≠NP, istniałaby formalna granica między szybkim sprawdzaniem a szybkim rozwiązywaniem.
Dwie klasy i jedno brakujące rozstrzygnięcie
P to zbiór problemów decyzyjnych, które można rozstrzygnąć w czasie ograniczonym wielomianem długości wejścia. NP można scharakteryzować jako problemy, dla których odpowiedź „tak” ma certyfikat możliwy do zweryfikowania w czasie wielomianowym. Ponieważ algorytm rozwiązujący problem może sam posłużyć jako sposób sprawdzenia odpowiedzi, P ⊆ NP. Cała tajemnica mieści się w pytaniu, czy zawieranie jest ścisłe. Clay Mathematics Institute nadal klasyfikuje P vs NP jako nierozwiązany Millennium Prize Problem.
Dlaczego nie wystarczy wskazać problemu, który „wydaje się trudny”
Dla wielu problemów NP-zupełnych przez dziesięciolecia nie znaleziono algorytmów wielomianowych, ale brak algorytmu nie jest dowodem, że taki algorytm nie istnieje. Historia informatyki zna problemy, których status poprawiał się dzięki nowym pomysłom. Aby dowieść P≠NP, trzeba wykazać matematycznie, że żadna deterministyczna procedura wielomianowa nie rozwiązuje przynajmniej jednego problemu z NP. To znacznie silniejsze twierdzenie niż obserwacja, że wszystkie znane metody są kosztowne.
Dlaczego NP-zupełność skupia uwagę
Problemy NP-zupełne są szczególne: każdy problem z NP można do nich zredukować w czasie wielomianowym. Jeśli znaleziono by wielomianowy algorytm dla jednego NP-zupełnego problemu, otrzymalibyśmy P=NP. Z drugiej strony dowód, że jeden z nich nie należy do P, dałby P≠NP. Właśnie dlatego SAT, 3-SAT, Hamiltonian Cycle i wiele innych problemów tworzą wspólny front tego samego pytania, mimo że opisują zupełnie różne rzeczy.
Co oznaczałoby P=NP — i czego nie oznacza
Równość P=NP nie sprawiłaby, że każdy trudny problem stałby się automatycznie łatwy w praktyce. Algorytm wielomianowy może mieć wysoki stopień wielomianu lub ogromne stałe. Co ważniejsze, P vs NP dotyczy modelu asymptotycznego i problemów decyzyjnych. Mimo to rozstrzygnięcie P=NP zmieniłoby teorię algorytmów: istniałaby ogólna możliwość efektywnego rozwiązywania wszystkich problemów NP poprzez redukcje do dowolnego NP-zupełnego problemu z algorytmem wielomianowym.
Stan na dziś
Brak rozstrzygnięcia jest częścią samej ciekawostki. Nie wolno przedstawiać P≠NP jako udowodnionego faktu, nawet jeśli jest to szeroko przyjmowana intuicja badawcza. Pewne jest natomiast, że pytanie jest precyzyjnie sformułowane, że P⊆NP oraz że konsekwencje rozwiązania są ogromne dla teorii obliczeń. Rekord wymaga okresowej weryfikacji właśnie dlatego, że status „nierozwiązany” może kiedyś ulec zmianie.
„Wielomianowy” nie jest synonimem „natychmiastowy”
Teoria P kontra NP abstrahuje od konkretnego procesora i pyta o zachowanie dla coraz większych wejść. Wielomian n^2 jest zwykle znacznie łagodniejszy niż 2^n, ale sama etykieta „w P” nie gwarantuje świetnej wydajności w każdej praktycznej skali. Algorytm może mieć wysoki stopień wielomianu, kosztowne stałe albo wymagać reprezentacji, która czyni małe przypadki nieporęcznymi. Z kolei algorytm o gorszej asymptotyce może wygrywać dla niewielkich danych. P kontra NP dotyczy więc fundamentalnej skalowalności w modelu obliczeń, a nie benchmarku jednego programu. To rozróżnienie chroni przed dwoma błędami naraz: „P oznacza praktycznie łatwe” oraz „NP-zupełne oznacza praktycznie niemożliwe”.