Problem P vs NP

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^[1][2].

Problem należy do siedmiu problemów milenijnych wskazanych przez Clay Mathematics Institute. Za jego rozwiązanie przewidziano nagrodę miliona dolarów^[2][1]. Jest powszechnie uważany za jedno z najważniejszych otwartych pytań informatyki teoretycznej^[3]. 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^[4].

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^[5]. 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ź^[6].

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^[6].

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^[7]. 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 ${\displaystyle 2^{o(n)},}$ gdzie ${\displaystyle n}$ 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^[8].

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^[9][10].

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^[11]. 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^[12].

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^[7][13]. 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^[14].

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”^[15]. 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^[3].

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^[15].

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 hierarchia wielomianowa(inne języki) 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^[16].

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. problem izomorfizmu grafów(inne języki) 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^[17][18][3].

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^[19]. Znane algorytmy dla tego problemu nie dają jednak klasycznego algorytmu wielomianowego. Istotnym postępem był quasi-wielomianowy algorytm László Babaiego^[20].

Decyzyjną wersję faktoryzacji można ująć jako pytanie, czy dla danych liczb naturalnych ${\displaystyle n}$ i ${\displaystyle k}$ istnieje dzielnik ${\displaystyle d}$ liczby ${\displaystyle n}$ taki, że ${\displaystyle 1<d<k.}$ 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^[18][16]. Z drugiej strony najlepsze klasyczne algorytmy faktoryzacji nie są wielomianowe, a algorytm Shora pokazuje wielomianową faktoryzację dopiero w modelu obliczeń kwantowych^[21]. Dla kontrastu samo rozpoznawanie liczb pierwszych ma deterministyczny algorytm wielomianowy dzięki wynikowi Agrawala, Kayala i Saxeny z 2004 roku^[22]. Dlatego faktoryzacja dobrze ilustruje, że problemy ważne kryptograficznie mogą znajdować się poza znanym podziałem na P i NP-zupełne.

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^[6]. 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^[23][24].

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^[6].

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 #P(inne języki) 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^[25]. Z klasycznym pytaniem P vs NP wiążą się także wyniki o zliczaniu i aproksymacji, w tym twierdzenie Tody, wiążące klasę PP(inne języki) z hierarchią wielomianową, oraz twierdzenie PCP, które precyzuje trudność znajdowania rozwiązań bliskich optymalnym^[26][27].

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 BPP(inne języki), a standardowym punktem odniesienia dla obliczeń kwantowych jest klasa BQP, obejmująca problemy rozwiązywalne przez komputer kwantowy z ograniczonym prawdopodobieństwem błędu^[28]. W parametryzowanej teorii złożoności podobną rolę odgrywa pytanie FPT kontra W[1], a w algebraicznej teorii złożoności pytanie VP kontra VNP^[29][30].

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^[4].

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^[31][32]. 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^[33].

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^[2][3]. 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”^[34]. Zaliczył je wówczas – obok hipotezy Riemanna i hipotezy Poincarégo – do trzech jego zdaniem największych otwartych problemów matematyki^[34].

• lista problemów NP-zupełnych

• Michael R.M.R. Garey Michael R.M.R., David S.D.S. Johnson David S.D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979, ISBN 978-0-7167-1045-5  (ang.).
• MichaelM. Sipser MichaelM., Introduction to the Theory of Computation, wyd. 3, Cengage Learning, 2013, ISBN 978-1-133-18779-0  (ang.).
• Christos H.Ch.H. Papadimitriou Christos H.Ch.H., Computational Complexity, Addison-Wesley, 1994, ISBN 978-0-201-53082-7  (ang.).
• SanjeevS. Arora SanjeevS., BoazB. Barak BoazB., Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN 978-0-521-42426-4  (ang.).