Największy problem informatyki: P vs NP

Istnieje siedem problemów matematycznych uznanych za tak trudne i ciekawe, że Instytut Matematyczny Claya ogłosił je problemami milenijnymi, a za rozwiązanie każdego z nich czeka nagroda w wysokości miliona dolarów. Jeden z tych problemów dotyczy także informatyki i nazywa się problem P vs NP. Wyjaśnijmy sobie, o co właściwie w tym problemie chodzi.

No dobra. Nie oszukujmy się, że łatwo będzie to wyjaśnić. To w końcu problem milenijny. Zaparz sobie więc dobrą zieloną herbatę 🍵 i do dzieła. Najpierw pokażemy sobie cztery różne problemy ze świata informatyki i algorytmów. Przeanalizujemy je i pokażemy, jaki mają związek z literkami P i NP.

Problem nr 1: Znalezienie najmniejszej liczby

P vs NP dotyczy algorytmów i ich złożoności. Wyobraź sobie, że wysypuję przed tobą sto karteczek, na każdej z nich jest zapisana jedna liczba, i chcę, żebyś znalazł karteczkę, na której jest zapisana najmniejsza liczba. Ile ci to zajmie?

Pół minuty? Dwie minuty?

To jednostki czasu, które w informatyce teoretycznej nie interesują nas aż tak bardzo. Interesuje nas raczej liczba operacji. Moglibyśmy więc zapytać trochę inaczej: ile karteczek muszę sprawdzić, żeby mieć pewność, że znalazłem najmniejszą liczbę? Odpowiedź brzmi: muszę sprawdzić wszystkie karteczki – bo najmniejsza liczba może być akurat na tej ostatniej. Kiedy rzucę przed tobą sto karteczek, musisz sprawdzić sto karteczek. Kiedy rzucę ich tysiąc, musisz sprawdzić tysiąc. Ogólnie: kiedy rzucę przed tobą n karteczek, musisz sprawdzić n karteczek.

To właśnie nazywamy złożonością algorytmów. Jeśli rzucę przed tobą n karteczek, a ty musisz wykonać n operacji, żeby znaleźć najmniejszą liczbę, oznacza to, że ten algorytm szukania najmniejszej liczby ma złożoność n, którą nazywamy też złożonością liniową, bo opisuje ją funkcja liniowa.

Dobrze, przejrzałeś sto karteczek i ogłosiłeś, że najmniejsza liczba to 17. W jaki sposób mogę sprawdzić, że mówisz prawdę? Nie ma innego sposobu niż znowu przejrzeć wszystkie karteczki i sprawdzić, że na żadnej z nich nie ma mniejszej liczby. Ty musisz więc obejrzeć n karteczek, żeby znaleźć najmniejszą liczbę, a ja, kiedy chcę to sprawdzić, muszę zrobić to samo. Złożoność weryfikacji wyniku też wynosi więc n, to złożoność liniowa.

Czy istnieją algorytmy, w których łatwiej jest sprawdzić wynik niż go znaleźć?

Problem nr 2: Iloczyn pary

Wyobraź sobie, że wysypuję przed tobą dwie równie duże kupki karteczek, na każdej karteczce znowu jest jedna liczba. I teraz chcę, żebyś znalazł liczbę z kupki A i liczbę z kupki B tak, żeby ich iloczyn dawał liczbę 918. Na przykład weźmy takie kupki liczb:

$$\begin{eqnarray} A &=& \left\{49, 11, 32, 54, 15\right\}\\ B &=&\left\{17, 64, 74, 61, 21\right\} \end{eqnarray}$$

W jaki sposób możemy znaleźć parę liczb, których iloczyn jest równy 918? No cóż, możemy po prostu wypróbować wszystkie możliwości. Ile ich będzie? Całkiem sporo, będzie ich 25. Zaczniemy od tego, że pomnożymy pierwszą liczbę z kupki A, czyli liczbę 49, przez każdą liczbę z kupki B:

$$\begin{eqnarray} 49\cdot17&=&833\\ 49\cdot64&=&3136\\ 49\cdot74&=&3626\\ 49\cdot61&=&2989\\ 49\cdot21&=&1029\\ \end{eqnarray}$$

Żadna para liczb nie daje 918. Spróbujemy więc tego samego z pozostałymi liczbami z kupki A, czyli kolejne pięć par dla liczby 11, kolejne pięć par dla liczby 32, kolejne pięć par dla 54 i ostatnie pięć par dla 15. W sumie możemy więc wypróbować 25 par liczb. Na koniec odkryjemy, że 54 · 17 = 918.

Jaka jest złożoność tego algorytmu? Będzie nas interesować, ile par liczb musieliśmy pomnożyć. Obie kupki zawierały po pięć karteczek, a my musieliśmy wypróbować każdą z pięciu liczb z pierwszej kupki z każdą z pięciu liczb z drugiej kupki. W sumie wypróbowaliśmy 5 · 5 = 25 kombinacji. Gdybym rzucił przed tobą dwie kupki po 10 karteczek, musiałbyś wypróbować 10 · 10 = 100 kombinacji. Uogólniając: jeśli rzucę przed tobą dwie kupki po n karteczek, musisz wypróbować n · n = n² kombinacji.

Powiemy, że ten nasz algorytm ma złożoność n², złożoność kwadratową, bo opisuje ją funkcja kwadratowa.

Ale jak trudno będzie sprawdzić wynik? Jeśli odpowiesz mi, że 54 i 17 to liczby, których iloczyn daje 918, nie muszę już przechodzić przez wszystkie pary liczb z obu kupek, jak musiałeś to robić ty. Wystarczy, że pomnożę tę jedną parę 54 · 17 i będę wiedział, czy masz rację, czy nie. Tak więc podczas gdy do rozwiązania tego problemu trzeba obliczyć aż n² iloczynów, do weryfikacji wystarczy obliczyć tylko jeden iloczyn. Weryfikacja ma więc złożoność stałą 1.

Pod tym względem to zadanie wyraźnie różni się od poprzedniego, w którym na samo obliczenie i na późniejszą weryfikację potrzebowaliśmy tyle samo kroków.

To zadanie jest też o rzędy wielkości trudniejsze od poprzedniego. Gdybym wysypał przed tobą dziesięć tysięcy karteczek i chciał, żebyś znalazł najmniejszą liczbę, pewnie dałbyś radę ją znaleźć w jeden dzień. Gdybym jednak wysypał przed tobą dwa razy po dziesięć tysięcy karteczek i kazał ci szukać iloczynu, musiałbyś sprawdzić dziesięć tysięcy razy dziesięć tysięcy iloczynów, co daje sto milionów obliczeń. Nawet gdybyś sprawdzał jeden iloczyn na sekundę, zajęłoby ci to około trzech lat.

Problem nr 3: Suma podzbioru

Pokażmy sobie trzeci problem. Tym razem wysypuję przed tobą dwanaście karteczek z liczbami i chcę, żebyś znalazł dowolną liczbę karteczek, których suma wynosi zero. Na przykład:

$$ A = \left\{24,-69{,}1,-15,-76,-60{,}16,-83{,}48,-22{,}54,-47\right\} $$

Wybierz z tych liczb dowolną grupę liczb, których suma wynosi 0. Na przykład liczby

$$24+48-69+1$$

dają sumę 4, więc nie są poprawną odpowiedzią. Poprawną odpowiedzią jest grupa liczb… i wiesz co? Spróbuj ją znaleźć sam w ramach pracy domowej 😉. Istnieje tylko jedna grupa liczb, których suma wynosi 0. Przynajmniej przekonasz się, jak trudny jest ten problem.

Teraz musimy poznać złożoność tego problemu. Samo obliczenie nie jest już całkiem trywialne i będzie raczej dla koneserów. Jeśli więc interesuje cię, jak można obliczyć złożoność tego problemu, czytaj dalej. W przeciwnym razie możesz przeskoczyć do następnego rozdziału. ⏩

W jaki sposób możemy więc znaleźć grupę liczb, których suma wynosi 0? No cóż, musimy po prostu wypróbować wszystkie możliwe kombinacje liczb. Musimy wypróbować wszystkie pary liczb, wszystkie trójki, czwórki, piątki itd. i przy każdej grupie sprawdzić, czy jej suma wynosi zero. Ile jest takich kombinacji?

Pokażmy to na mniejszym zbiorze liczb. Ile różnych grup liczb, czyli podzbiorów, mogę utworzyć z trójki liczb B = {5, 7, 9}? Jest ich w sumie osiem:

$$\begin{eqnarray} B_1&=&\left\{\right\}\\ B_2&=&\left\{5\right\}\\ B_3&=&\left\{7\right\}\\ B_4&=&\left\{9\right\}\\ B_5&=&\left\{5{,}9\right\}\\ B_6&=&\left\{5{,}7\right\}\\ B_7&=&\left\{7, 9\right\}\\ B_8&=&\left\{5{,}7,9\right\}\\ \end{eqnarray}$$

Zauważ, że policzyliśmy też podzbiór pusty B₁. Teraz nie jest zbyt przydatny, ale dla porządku go zostawiliśmy. Żeby uprościć sobie obliczenia, przyporządkujemy każdemu podzbiorowi wektor binarny. Wektor binarny to po prostu ciąg zer i jedynek, na przykład 00101010. My będziemy pracować z wektorami binarnymi o długości trzy. Wektory przyporządkujemy tak, że 101 przyporządkujemy podzbiorowi, który zawiera „pierwszą i trzecią liczbę z wyjściowego zbioru, ale nie drugą liczbę”, czyli zbiorowi {5, 9}. Wektor 110 przyporządkujemy podzbiorowi, który zawiera „pierwszą i drugą liczbę z wyjściowego zbioru, ale nie trzecią”, czyli zbiorowi {5, 7} itd.

$$\begin{eqnarray} B_1=\left\{\right\}&\rightarrow&000\\ B_2=\left\{5\right\}&\rightarrow&100\\ B_3=\left\{7\right\}&\rightarrow&010\\ B_4=\left\{9\right\}&\rightarrow&001\\ B_5=\left\{5{,}9\right\}&\rightarrow&101\\ B_6=\left\{5{,}7\right\}&\rightarrow&110\\ B_7=\left\{7, 9\right\}&\rightarrow&011\\ B_8=\left\{5{,}7,9\right\}&\rightarrow&111\\ \end{eqnarray}$$

Widzimy, że każdy podzbiór ma dokładnie jeden wektor binarny o długości trzy. I każdy wektor binarny o długości trzy odpowiada dokładnie jednemu podzbiorowi. Jeśli więc obliczymy, ile jest różnych wektorów binarnych o długości n, dostaniemy liczbę różnych kombinacji, które da się złożyć, gdy na wejściu mamy n różnych liczb. Policzmy to więc.

Wektory binarne o długości jeden są dwa: 0 i 1.

Wektory binarne o długości dwa dostaniemy tak, że weźmiemy wszystkie wektory binarne o długości jeden i na końcu każdego wektora dopiszemy 0: dostaniemy wektory 00 i 10. Znowu weźmiemy wszystkie wektory o długości 1 i dopiszemy na końcu 1: 01 i 11. W ten sposób dostaliśmy wszystkie wektory o długości 2: 00, 01, 10 i 11.

Wektory binarne o długości trzy dostaniemy tak, że weźmiemy wszystkie wektory binarne o długości dwa i dopiszemy na końcu zero: 000, 010, 100 i 110, oraz jedynkę: 001, 011, 101 i 111.

I tak dalej dla każdej kolejnej długości. Widzimy, że gdy zwiększymy długość wektora binarnego o jeden, liczba różnych wektorów binarnych wzrośnie dwukrotnie. Dla wektora o długości cztery dostalibyśmy więc w sumie 2 · 2 · 2 · 2, czyli 16, różnych kombinacji.

Ogólnie możemy wywnioskować, że jeśli mamy zbiór M, który zawiera n elementów, to liczba wszystkich podzbiorów tego zbioru M jest równa liczbie wszystkich różnych wektorów binarnych o długości n, a ta jest równa

$$\underbrace{2\cdot2\cdot\ldots\cdot2}_{n-\mbox{krotnie}}=2^n$$

2ⁿ czy n² – co za różnica? 🤷‍♂

Istnieje więc 2ⁿ różnych podzbiorów, które możemy utworzyć ze zbioru n liczb. W naszym przypadku mamy n = 12 liczb, musimy więc sprawdzić 2¹² różnych kombinacji, czyli 4096 kombinacji. Powiemy, że ten problem ma złożoność 2ⁿ, złożoność wykładniczą, bo opisuje go funkcja wykładnicza.

Zauważ, że poprzedni problem miał złożoność n², a ten ma złożoność 2ⁿ. Wygląda to bardzo podobnie, prawda? Tyle że jest wielka różnica między tym, czy wykładnik jest stały, czy jest w nim zmienna n. Zauważ, że gdy n = 4, dostaniemy

$$\begin{eqnarray} n^2&=&4^2&=&16\\ 2^n&=&2^4&=&16 \end{eqnarray}$$

Dobrze, na razie wychodzi nam to samo. A co, gdy n = 10?

$$\begin{eqnarray} n^2&=&10^2&=&100\\ 2^n&=&2^{10}&=&1024 \end{eqnarray}$$

Ojej, funkcja wykładnicza wystrzeliła w górę i nagle jest mniej więcej dziesięć razy większa niż kwadratowa. A co dostaniemy dla n = 20?

$$\begin{eqnarray} n^2&=&20^2&=&400\\ 2^n&=&2^{20}&=&1~048~576 \end{eqnarray}$$

Złożoność wykładnicza ma dla n = 20 wartość mniej więcej 2600 razy większą niż złożoność kwadratowa. Widzimy więc, że funkcja wykładnicza rośnie dużo szybciej niż funkcja kwadratowa. Przypomnij sobie o tym, kiedy znowu dopadnie nas jakaś pandemia, która będzie się szerzyć w populacji w tempie wykładniczym.

Gdybym więc rzucił przed tobą dwadzieścia karteczek, musiałbyś sprawdzić 1 048 576 kombinacji. To całkiem sporo.

Jak sprawdzimy poprawność wyniku?

Ile czasu zajmie mi sprawdzenie, że wskazana grupa liczb naprawdę daje sumę 0? To będzie dość szybkie, po prostu dodam do siebie liczby z tej jednej grupy i jeśli ich suma będzie równa 0, to znalazłeś właściwą grupę karteczek, a jeśli suma będzie inna, znalazłeś zły zestaw karteczek.

Znowu widzimy, że sprawdzić wynik jest o rzędy wielkości łatwiej, niż go znaleźć.

Problem nr 4: Problem komiwojażera

Problem komiwojażera to jeden z najsłynniejszych problemów algorytmicznych. Z grubsza rzecz biorąc, mamy komiwojażera, czyli wędrownego sprzedawcę, który handluje deszczem. I ten komiwojażer musi dużo podróżować, żeby na siebie zarobić. Postanowił więc, że odwiedzi 14 największych miast w Polsce. A ponieważ nie chce niczego marnować, postanowił, że znajdzie najkrótszą możliwą trasę, która przeprowadzi go przez wszystkie te miasta. A naszym zadaniem jest taką najkrótszą trasę znaleźć.

Jak możemy tę najkrótszą trasę znaleźć? Wypróbujemy wszystkie możliwości.

Możemy to sobie uprościć. Wyobraźmy sobie, że między każdymi dwoma miastami istnieje dokładnie jedna najkrótsza droga. W jaki sposób możemy znaleźć najkrótszą trasę przez wszystkie miasta? Miast mamy 14. Mamy więc 14 możliwości, gdzie zacząć. Powiedzmy, że zaczęliśmy w Łodzi! Dokąd możemy się dostać z Łodzi? Teoretycznie możemy pojechać do dowolnego innego miasta. Możemy więc wybierać spośród 13 pozostałych miast.

Już teraz możemy policzyć, że mamy w sumie 14 · 13 możliwości odwiedzenia dwóch pierwszych miast – mamy 14 możliwości, gdzie zacząć, a potem do wyboru 13 pozostałych miast.

Kiedy dojedziemy do drugiego miasta, musimy jechać dalej. W dwóch miastach już byliśmy, więc możemy pojechać do jednego z 12 pozostałych miast. Mamy więc w sumie 14 · 13 · 12 możliwości odwiedzenia pierwszych trzech miast.

Kiedy odwiedzimy trzecie miasto, musimy wybrać jedno z 11 pozostałych miast, potem jedno z 10 pozostałych miast itd.

Kiedy odwiedzimy wszystkie, okaże się, że mieliśmy do wyboru w sumie

$$14\cdot13\cdot12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$$

możliwości. To może ci przypominać silnię, którą oznaczamy wykrzyknikiem. Możemy więc powiedzieć, że ten iloczyn jest równy 14!:

$$14!=14\cdot13\cdot12\cdot11\cdot10\cdot9\cdot8\cdot7\cdot6\cdot5\cdot4\cdot3\cdot2\cdot1$$

a więc istnieje 14! tras, które prowadzą przez wszystkie te miasta. Czy to dużo? Całkiem sporo, bo

$$14!=87~178~291~200.$$

Ogólnie, gdybyśmy szukali najkrótszej trasy przez n miast, musielibyśmy wypróbować n! różnych tras. Złożoność tego rozwiązania wynosi więc n!.

Jak sprawdzilibyśmy, że znaleźliśmy poprawny wynik? Gdybyś mi powiedział, że najkrótsza trasa prowadzi z Poznania do Łodzi, potem do Wrocławia itd., jak mogę sprawdzić, że mówisz prawdę? No, raczej ciężko 🤷‍♂. Bo kiedy patrzę na tę trasę, nie mam jak łatwo sprawdzić, czy akurat ona jest najkrótsza. Właściwie muszę przeprowadzić całe obliczenie od nowa. Weryfikacja wyniku ma więc też złożoność n!.

Klasy P i NP

Przedstawiliśmy cztery problemy i algorytmy, które je rozwiązują, i przeanalizowaliśmy, jak trudno jest znaleźć rozwiązanie i jak trudno je sprawdzić. Możemy to podsumować w tej tabeli:

Teraz podzielimy nasze problemy na dwie grupy. Pierwszą grupę będą tworzyć problemy, które są łatwe do rozwiązania. To problemy, które można rozwiązać ze złożonością n albo n² albo n³ albo n⁴ itd. Ponieważ wyrażenia takie jak n² nazywamy wielomianami, tę klasę złożoności oznaczamy literą P (od angielskiego polynomial, czyli wielomianowy). Mówimy więc, że klasa P zawiera problemy, które da się rozwiązać w czasie wielomianowym (= mają złożoność na przykład n² albo n⁷), czyli takie, dla których istnieje algorytm wielomianowy. Ogólnie są to problemy, które da się rozwiązać mniej więcej łatwo.

Do klasy P należy więc problem nr 1, znalezienie najmniejszej liczby, bo ma złożoność rozwiązania n, a także problem nr 2, iloczyn pary, bo jego złożoność rozwiązania wynosi n², a jedno i drugie to wielomiany.

Drugą klasą jest klasa NP. Zawiera ona problemy, których rozwiązanie da się sprawdzić w czasie wielomianowym. Do klasy NP należą więc wszystkie problemy oprócz ostatniego. Problemu komiwojażera nie umiemy sprawdzić w czasie wielomianowym. Trzy poprzednie problemy da się sprawdzić w czasie wielomianowym.

Problemu komiwojażera nie umiemy ani rozwiązać, ani sprawdzić w czasie wielomianowym. Dla problemu komiwojażera potrzebowalibyśmy więc jeszcze jednej klasy, która zawierałaby jeszcze trudniejsze problemy. Taka klasa istnieje, ale w tej chwili nie jest dla nas interesująca.

Jasne jest, że klasa P jest podzbiorem klasy NP. Czyli każdy problem, który jest w klasie P, jest jednocześnie w klasie NP. Ma to sens – jeśli potrafimy jakiś problem rozwiązać w czasie wielomianowym, potrafimy też w czasie wielomianowym sprawdzić wynik.

Problem P vs NP

A czy działa to też w drugą stronę? Czy każdy problem z klasy NP jest jednocześnie w klasie P? Czyli: jeśli istnieje sposób, jak w czasie wielomianowym sprawdzić wynik problemu, czy istnieje też algorytm, który rozwiązywałby ten problem w czasie wielomianowym?

Na przykład wiemy, że potrafimy w czasie wielomianowym sprawdzić wynik problemu nr 3, sumy podzbioru. Ale do jego rozwiązania użyliśmy algorytmu, który nie jest wielomianowy, użyty algorytm ma złożoność wykładniczą 2ⁿ. Czy jednak wiemy na pewno, że dla tego problemu nie istnieje żaden algorytm o złożoności wielomianowej?

Nie wiemy!

Równie dobrze mogłoby się okazać, że dla każdego problemu, który da się sprawdzić w czasie wielomianowym, istnieje algorytm, który ten problem rozwiązuje w czasie wielomianowym. Nie wiemy tego. Nie umiemy udowodnić istnienia takiego algorytmu, ale nie umiemy też wykluczyć jego istnienia.

Gdyby dla każdego problemu z klasy NP istniał algorytm, który rozwiązuje go w czasie wielomianowym, oznaczałoby to, że klasa NP jest właściwie równa klasie P. Wszystkie problemy z klasy P byłyby w klasie NP i wszystkie problemy z klasy NP byłyby w klasie P – obie klasy byłyby równe, byłyby identyczne.

Problem P vs NP to więc pytanie, czy klasa P jest identyczna z klasą NP, czy też są to dwie różne klasy problemów.

Zachodzi więc albo P = NP, albo P ≠ NP. Tego nikt nie wie, a jeśli to odkryjesz, czeka cię nagroda miliona dolarów, nieśmiertelna sława i prawdopodobnie także Nagroda Turinga, czyli taki Nobel dla informatyków.

Co by się stało, gdyby P = NP?

Co by się stało, gdyby zachodziło P = NP? No cóż, nie tak łatwo powiedzieć, co by się stało. Wiedzielibyśmy, że dla wszystkich problemów z klasy NP istnieje algorytm, który rozwiązuje je w czasie wielomianowym. Na przykład że dla naszego problemu nr 3, sumy podzbioru, istnieje algorytm, który rozwiązuje go w czasie wielomianowym. Tyle że ma to trzy haczyki:

• To, że wiedzielibyśmy, że taki algorytm istnieje, nie znaczy, że potrafilibyśmy go znaleźć. Po prostu wiedzielibyśmy, że tak, istnieje algorytm, który rozwiązuje problem w czasie wielomianowym, ale moglibyśmy nie umieć go skonstruować na przykład przez kolejne sto lat. To trochę jak z tym, że ogólna teoria względności przewidziała istnienie czarnych dziur, a mimo to minęło jeszcze kilka dziesięcioleci, zanim udało nam się zrobić pierwsze „zdjęcie” czarnej dziury.
• To, że istnieje algorytm działający w czasie wielomianowym, niestety jeszcze nie znaczy, że jest szybki. Moglibyśmy znaleźć algorytm o złożoności n¹⁰⁰. Bo także wyrażenie n¹⁰⁰ jest wielomianem. Kiedy porównamy złożoności 2ⁿ i n¹⁰⁰, okaże się, że dopóki n jest stosunkowo małe, algorytm o złożoności 2ⁿ wciąż potrzebuje mniej operacji. Na przykład dla n = 20 zachodzi 2²⁰ = 1 048 576, podczas gdy wyrażenie 20¹⁰⁰ daje liczbę, która ma około 130 cyfr, czyli liczbę o 120 rzędów wielkości większą niż 1 048 576. Nasz algorytm wielomianowy byłby więc w rzeczywistości wolniejszy niż ten wykładniczy. Przynajmniej dopóki n jest stosunkowo małe.
• Gdyby jednak udało nam się znaleźć szybki algorytm działający w czasie wielomianowym, moglibyśmy wiele problemów rozwiązywać szybciej i dokładniej. To oczywiście dobra wiadomość, ale ma to też swoje minusy. Istnieje dziedzina, która opiera się na tym, że niektóre problemy są trudne do rozwiązania, a jest nią kryptografia – szyfrowanie. Mogłoby się więc okazać, że złamanie obecnych szyfrów stałoby się o rzędy wielkości łatwiejsze.

Przerywnik: skoro doczytałeś aż tutaj, w nagrodę zdradzę ci, że rozwiązaniem problemu nr 3 jest 24 + 1 − 60 + 16 − 83 + 48 + 54.

Co by się stało, gdyby P ≠ NP?

Gdyby się okazało, że klasy problemów P i NP są różne, nie stałoby się aż tak wiele, bo to mniej więcej status quo. W tej chwili nie mamy żadnego algorytmu, który rozwiązywałby jakiś trudny problem z NP w czasie wielomianowym, i gdyby ktoś udowodnił, że P ≠ NP, to po prostu tak by zostało na zawsze. Dużo większą sensacją byłby dowód, że P = NP.

Nawiązania w popkulturze

• W jednym z odcinków Simpsonów widzimy, jak Homer trafia do jakiejś alternatywnej rzeczywistości, w której ukazuje mu się, że P = NP. Do obejrzenia na youtube.com.
• Z kolei w Futuramie widzimy, że w magazynie mają dwie teczki, jedną z napisem P i drugą z napisem NP. Do obejrzenia na youtube.com.
• Drugi odcinek drugiego sezonu serialu Elementary, zatytułowany „Solve for X”, opowiadał o morderstwie matematyka, który prawdopodobnie rozwiązał problem P vs NP.