Problem P vs NP (także pytanie, czy P = NP) – nierozwiązany problem teorii złożoności obliczeniowej dotyczący tego, czy klasa złożoności P jest równa klasie NP. W ujęciu nieformalnym jest to pytanie, czy każdy problem, dla którego poprawność podanego rozwiązania można szybko sprawdzić, można również szybko rozwiązać. Słowo „szybko” oznacza tu istnienie algorytmu działającego w czasie wielomianowym względem rozmiaru danych wejściowych.

Problem należy do siedmiu problemów milenijnych wskazanych przez Clay Mathematics Institute. Za jego rozwiązanie przewidziano nagrodę miliona dolarów. Jest powszechnie uważany za jedno z najważniejszych otwartych pytań informatyki teoretycznej. Mimo tej rangi nie należy utożsamiać czasu wielomianowego z praktyczną łatwością: algorytm wielomianowy może mieć zbyt duże stałe lub wykładniki, a niektóre problemy spoza tej klasy mogą być rozwiązywane skutecznie w wielu typowych przypadkach.

mały|Schemat relacji między klasami P i NP oraz problemami NP-zupełnymi i NP-trudnymi w przypadkach P ≠ NP oraz P = NP.

Sformułowanie Klasa P obejmuje problemy decyzyjne, które można rozwiązać na deterministycznym modelu obliczeń w czasie wielomianowym. Formalnie są to języki akceptowane przez deterministyczną maszynę Turinga w liczbie kroków ograniczonej wielomianem od długości wejścia. Klasa NP obejmuje problemy decyzyjne, dla których odpowiedź „tak” można zweryfikować w czasie wielomianowym, jeżeli podany jest odpowiedni certyfikat rozwiązania. Definicja przez certyfikaty jest równoważna standardowej definicji przez niedeterministyczną maszynę Turinga działającą w czasie wielomianowym. Każdy problem z P należy do NP, ponieważ algorytm rozwiązujący pozwala też szybko zweryfikować odpowiedź.

Pytanie P versus NP dotyczy tego, czy zachodzi również inkluzja odwrotna, czyli czy P = NP. Jeżeli P = NP, każdy problem z szybko weryfikowalnym rozwiązaniem miałby także algorytm znajdujący rozwiązanie w czasie wielomianowym. Jeżeli P ≠ NP, istnieją problemy, których rozwiązania da się szybko sprawdzać, ale których nie da się rozwiązywać w czasie wielomianowym.

Przykład intuicyjny Typowym przykładem jest problem spełnialności formuł logicznych. Dla danej formuły rachunku zdań łatwo sprawdzić, czy konkretne przypisanie wartości logicznych spełnia tę formułę: wystarczy podstawić wartości zmiennych i obliczyć wynik. Znacznie trudniejsze może być znalezienie takiego przypisania lub stwierdzenie, że ono nie istnieje. Problem spełnialności, znany jako SAT, jest centralnym przykładem problemu NP-zupełnego. Z SAT wiąże się silniejsza od hipotezy P ≠ NP hipoteza czasu wykładniczego, według której 3-SAT nie ma algorytmu podwykładniczego, tj. działającego w czasie gdzie oznacza liczbę zmiennych formuły. Impagliazzo, Paturi i Zane pokazali, że podwykładnicze algorytmy dla wielu naturalnych problemów NP-zupełnych są powiązane redukcjami zachowującymi taki czas działania.

Podobny kontrast między łatwym sprawdzeniem a trudnym znalezieniem rozwiązania występuje w wielu łamigłówkach i zadaniach kombinatorycznych. Uzupełnioną planszę uogólnionego sudoku albo kwadrat łaciński łatwo zweryfikować, lecz istnienie takiego wypełnienia dla uogólnionego sudoku oraz uzupełnianie częściowych kwadratów łacińskich to problemy NP-zupełne.

Historia Wcześniejsze intuicje podobnych trudności pojawiały się jeszcze przed formalnym zdefiniowaniem klas P i NP. W 1955 roku John Nash w liście do National Security Agency rozważał zależność między długością klucza kryptograficznego a trudnością jego złamania. Rok później Kurt Gödel pytał Johna von Neumanna o możliwość szybkiego rozstrzygania problemów dowodzenia twierdzeń. Później zwracano uwagę, że list ten zapowiadał część motywacji stojących za problemem P versus NP.

Pierwszym naturalnym problemem, dla którego wykazano NP-zupełność, był problem spełnialności formuł logicznych. Wynik ten, znany jako twierdzenie Cooka-Levina, został sformułowany przez Stephena Cooka w 1971 roku, a niezależnie w pokrewnej postaci przez Leonida Levina. W 1972 roku Richard Karp pokazał metodę sprowadzania SAT do wielu innych problemów kombinatorycznych i wyodrębnił 21 klasycznych problemów NP-zupełnych, co utrwaliło redukcje wielomianowe jako podstawowe narzędzie badania P vs NP.

NP-zupełność i NP-trudność W badaniu problemu P versus NP kluczową rolę odgrywają problemy NP-zupełne. Są to problemy należące do NP, do których każdy problem z NP można sprowadzić za pomocą redukcji wielomianowej. W typowym ujęciu taka redukcja jest funkcją obliczalną w czasie wielomianowym, która przekształca instancje jednego problemu w instancje drugiego, zachowując odpowiedź „tak” albo „nie”. Oznacza to, że szybki algorytm dla dowolnego problemu NP-zupełnego dawałby szybkie algorytmy dla wszystkich problemów z NP. W konsekwencji wykazanie, że choć jeden problem NP-zupełny należy do P, dowiodłoby równości P = NP.

Pojęciem szerszym jest NP-trudność. Problem NP-trudny to taki, do którego można zredukować każdy problem z NP. Nie musi on jednak sam należeć do NP ani nawet być problemem decyzyjnym. Problem NP-zupełny jest więc jednocześnie NP-trudny i należy do NP.

Z równością P = NP wiąże się też pytanie o zapadanie się szerszych klas złożoności. Gdyby P było równe NP, równe byłyby także NP i co-NP, a zapadłaby się do P. Większość badaczy uważa to za mało prawdopodobne, co jest jednym z powodów ostrożnego traktowania hipotezy P = NP.

Problemy NP-pośrednie Jeżeli P ≠ NP, nie wszystkie problemy z NP muszą być NP-zupełne. Twierdzenie Ladnera pokazuje, że przy tym założeniu istnieją problemy pośrednie: należące do NP, ale nienależące ani do P, ani do klasy problemów NP-zupełnych. Jako kandydatów na takie problemy często wskazuje się m.in. oraz decyzyjne wersje logarytmu dyskretnego i rozkładu liczby całkowitej na czynniki, choć ich dokładne miejsce w klasycznej hierarchii złożoności pozostaje otwarte.

Dla izomorfizmu grafów znane są dodatkowe przesłanki strukturalne: gdyby problem ten był NP-zupełny, hierarchia wielomianowa zapadłaby się do drugiego poziomu, co uważa się za mało prawdopodobne. Znane algorytmy dla tego problemu nie dają jednak klasycznego algorytmu wielomianowego. Istotnym postępem był quasi-wielomianowy algorytm László Babaiego.

Decyzyjną wersję faktoryzacji można ująć jako pytanie, czy dla danych liczb naturalnych i istnieje dzielnik liczby taki, że Problem ten należy do NP i co-NP, a nawet do klas UP i co-UP. Gdyby był NP-zupełny, hierarchia wielomianowa zapadłaby się do pierwszego poziomu. Z drugiej strony najlepsze klasyczne algorytmy faktoryzacji nie są wielomianowe, a algorytm Shora pokazuje wielomianową faktoryzację dopiero w modelu obliczeń kwantowych. Dla kontrastu samo rozpoznawanie liczb pierwszych ma deterministyczny algorytm wielomianowy dzięki wynikowi Agrawala, Kayala i Saxeny z 2004 roku. Dlatego faktoryzacja dobrze ilustruje, że problemy ważne kryptograficznie mogą znajdować się poza znanym podziałem na P i NP-zupełne.

Problemy trudniejsze i pokrewne Pytanie P vs NP nie oznacza, że wszystkie problemy obliczeniowe mieszczą się w jednej z tych dwóch klas. Z twierdzeń hierarchii czasowej wynika, że P jest właściwie zawarte w EXPTIME, więc istnieją problemy rozwiązywalne w czasie wykładniczym, których nie da się rozwiązać w czasie wielomianowym. W literaturze jako przykłady naturalnych problemów o bardzo wysokiej złożoności analizowano m.in. uogólnione wersje gier planszowych oraz rozstrzyganie formuł arytmetyki Presburgera.

Z tego powodu problem P vs NP jest tylko jednym z pytań o granice efektywnego obliczania, choć pytaniem centralnym. Rozstrzygnięcie P ≠ NP oddzieliłoby P od części NP, ale nie wyczerpałoby klasyfikacji zadań jeszcze trudniejszych, problemów nierozstrzygalnych ani zadań liczbowych i aproksymacyjnych, które wymagają osobnych narzędzi teorii złożoności.

Samo pytanie P vs NP dotyczy problemów decyzyjnych, czyli takich z odpowiedzią „tak” albo „nie”. W teorii złożoności bada się jednak również problemy liczenia rozwiązań. Klasa obejmuje zadania, w których trzeba policzyć liczbę certyfikatów spełniających warunek. Leslie Valiant pokazał, że takie problemy mogą być bardzo trudne nawet wtedy, gdy samo stwierdzenie istnienia rozwiązania jest łatwe. Z klasycznym pytaniem P vs NP wiążą się także wyniki o zliczaniu i aproksymacji, w tym twierdzenie Tody, wiążące klasę z hierarchią wielomianową, oraz twierdzenie PCP, które precyzuje trudność znajdowania rozwiązań bliskich optymalnym.

Część pokrewnych problemów wykracza poza klasyczny model deterministycznej maszyny Turinga używany w definicjach P i NP. W szczególności obliczenia losowe i kwantowe prowadzą do osobnych klas złożoności. Nie są one po prostu wariantem pytania P vs NP, lecz pokazują, że pojęcie efektywnego obliczania zależy także od przyjętego modelu. Obliczenia losowe opisuje m.in. klasa , a standardowym punktem odniesienia dla obliczeń kwantowych jest klasa BQP, obejmująca problemy rozwiązywalne przez komputer kwantowy z ograniczonym prawdopodobieństwem błędu. W parametryzowanej teorii złożoności podobną rolę odgrywa pytanie FPT kontra W, a w algebraicznej teorii złożoności pytanie VP kontra VNP.

Czas wielomianowy a praktyczna obliczalność Czas wielomianowy jest w teorii złożoności podstawowym formalnym progiem efektywnego obliczania, ale nie jest tym samym co praktyczna łatwość. Algorytm wielomianowy może mieć bardzo duży wykładnik lub stałe ukryte w notacji asymptotycznej, a twierdzenie o samym istnieniu takiego algorytmu mogłoby nie dawać od razu użytecznej procedury obliczeniowej.

Również odwrotna intuicja bywa zawodna: problem może mieć złe ograniczenia w najgorszym przypadku, a mimo to dobrze działać w wielu zastosowaniach. Dla niektórych reguł wyboru pivota metoda sympleks ma wykładnicze przykłady najgorszego przypadku, choć w praktyce często jest skuteczna. Samo programowanie liniowe ma natomiast znane algorytmy wielomianowe. Problem P vs NP nie rozstrzyga też automatycznie złożoności średniej: możliwe jest, że problem trudny w najgorszym przypadku ma większość instancji łatwych w praktyce. Russell Impagliazzo opisał kilka hipotetycznych „światów” złożoności średniej, od pełnej algorytmicznej łatwości po świat kryptograficznie trudnych instancji.

Znaczenie Rozwiązanie problemu miałoby daleko idące konsekwencje dla informatyki teoretycznej i wielu zastosowań. Jego znaczenie wynika z tego, że wiele naturalnych zadań optymalizacyjnych, logicznych i kombinatorycznych można wyrazić jako problemy w NP albo przez redukcje powiązać z problemami NP-zupełnymi. Matematyk Stephen Smale umieścił pytanie „czy P = NP?” jako trzecie na swojej liście problemów matematycznych na XXI wiek (1998) i nazwał je „darem informatyki dla matematyki”. Zaliczył je wówczas – obok hipotezy Riemanna i hipotezy Poincarégo – do trzech jego zdaniem największych otwartych problemów matematyki.

Konsekwencje P = NP Dowód P = NP, zwłaszcza gdyby prowadził do praktycznych algorytmów, mógłby radykalnie zmienić optymalizację, automatyczne dowodzenie twierdzeń, projektowanie algorytmów i kryptografię. Samo formalne P = NP nie musiałoby oznaczać złamania współczesnej kryptografii, bo dowód mógłby nie dawać użytecznego algorytmu, jednak efektywny algorytm dla problemów NP-zupełnych miałby poważne konsekwencje.

Praktyczny algorytm dla szerokiej klasy NP-zupełnej mógłby wpływać nie tylko na kryptografię, lecz także na optymalizację i nauki przyrodnicze, ponieważ problemy NP-zupełne pojawiają się m.in. w programowaniu całkowitoliczbowym i problemie komiwojażera oraz uproszczonych modelach zwijania białek. W matematyce praktyczny algorytm znajdowania krótkich dowodów mógłby zmienić sposób rozwiązywania problemów, bo poprawność formalnego dowodu da się sprawdzić w czasie wielomianowym. Podkreślali to m.in. Gödel w liście do von Neumanna oraz Cook w opisie problemu milenijnego.

Konsekwencje P ≠ NP