Problem P vs NP 📖 Wikipedia

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.

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)}}$ . 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 antycypował 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.

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 problemów takich jak logarytm dyskretny i rozkład liczby całkowitej na czynniki, choć ich dokładne miejsce w klasycznej hierarchii złożoności pozostaje otwarte^[17][18].

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]. 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, choć centralnym, pytaniem o granice efektywnego obliczania. Rozstrzygnięcie P ≠ NP oddzieliłoby P od części NP, ale nie wyczerpałoby klasyfikacji problemów 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 #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(inne języki), 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^[31][32].

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^[33][34]. 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^[35].

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].

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

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^[15] oraz uproszczonych modelach zwijania białek^[36]. 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^[37][2].

Dowód P ≠ NP potwierdziłby formalnie, że istnieje zasadnicza różnica między szybkim sprawdzaniem a szybkim znajdowaniem rozwiązań. Miałby głównie znaczenie teoretyczne, ale uporządkowałby badania nad problemami trudnymi: dla wielu naturalnych zadań nie należałoby oczekiwać algorytmu wielomianowego dla wszystkich przypadków. Wzmacniałoby to rolę algorytmów przybliżonych i heurystyk^[38].

Nie jest znany dowód ani P = NP, ani P ≠ NP. Wśród badaczy dominuje przekonanie, że P ≠ NP, ale pozostaje ono hipotezą, a nie twierdzeniem. W ankiecie Williama Gasarcha z 2018 roku większość respondentów, a wśród osób zaklasyfikowanych jako eksperci prawie wszyscy, deklarowała oczekiwanie, że P ≠ NP. Autor podkreślał jednak, że takie ankiety opisują opinie środowiska, a nie stanowią dowodu matematycznego^[39]. Lance Fortnow podkreślał, że mimo ogromnej liczby prac nad problemami NP-zupełnymi nie znaleziono algorytmu wielomianowego dla żadnego z nich ani dowodu, że taki algorytm nie istnieje^[3].

Ze względu na rangę problemu regularnie pojawiają się deklarowane rozwiązania, lecz zestawienia takich prób traktują je jako niezweryfikowane albo obalone, a żaden dowód nie został przyjęty przez środowisko^[40].

Badania nad problemem ujawniły także ograniczenia wielu naturalnych metod dowodzenia. W 1975 roku Theodore Baker, John Gill i Robert Solovay pokazali, że istnieją relatywizowane światy obliczeń, w których zachodzi P = NP, oraz takie, w których P ≠ NP. Oznacza to, że techniki dowodowe zachowujące się jednakowo względem wszystkich wyroczni nie mogą same rozstrzygnąć problemu^[41]. Później wskazywano kolejne bariery, m.in. dla tzw. dowodów naturalnych w złożoności obwodowej oraz dla algebryzacji, co częściowo tłumaczy, dlaczego standardowe podejścia do dolnych ograniczeń złożoności nie wystarczyły dotąd do rozwiązania problemu^[42][43].

Rozważano też niezależność problemu od standardowych systemów aksjomatycznych. Znane wyniki są jednak ostrożne: niezależność od słabszych teorii arytmetyki pociągałaby mocne konsekwencje algorytmiczne, a analizy metamatematyczne muszą być zgodne z istnieniem albo nieistnieniem efektywnych algorytmów dla problemów z NP^[44][45].

Problem P vs NP ma również charakter logiczny. Twierdzenie Fagina opisuje klasę NP jako własności struktur skończonych wyrażalne w egzystencjalnej logice drugiego rzędu, a późniejsze wyniki teorii złożoności opisowej wiążą P z logiką pierwszego rzędu rozszerzoną o operator najmniejszego punktu stałego, przy uporządkowanych strukturach skończonych. W tym języku pytanie P vs NP można odczytać jako pytanie, czy egzystencjalne kwantyfikowanie po relacjach daje większą siłę wyrazu niż odpowiednia logika punktu stałego^[46][47]. W tym ujęciu, jak zauważa Elvira Mayordomo, równość P = NP byłaby równoważna temu, że egzystencjalna logika drugiego rzędu nie opisuje nad uporządkowanymi strukturami skończonymi więcej języków niż logika punktu stałego^[48].

• 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.).