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.

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.

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

Problem P vs 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ę hipoteza czasu wykładniczego, silniejsza od hipotezy P ≠ NP. Według niej 3-SAT nie ma algorytmu podwykładniczego, czyli działającego w czasie gdzie to liczba zmiennych formuły, a oznacza funkcję rosnącą asymptotycznie wolniej niż 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 vs 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 vs 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 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.

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

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

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

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. Przy niektórych regułach wyboru kolejnego wierzchołka (tzw. regułach 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ę. Równość P = NP oznaczałaby, że fałszywe są założenia o trudności obliczeniowej, na których opiera się bezpieczeństwo współczesnej kryptografii, np. założenie o trudności rozkładu liczb całkowitych na czynniki. Nie musiałaby jednak od razu umożliwić praktycznego łamania stosowanych systemów, bo dowód mógłby być niekonstruktywny i nie dawać użytecznego algorytmu. Dopiero praktyczny algorytm dla problemu NP-zupełnego miałby dla kryptografii katastrofalne skutki.

Taki algorytm 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

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 metod heurystycznych.

Status badań

Opinie badaczy i zgłaszane rozwiązania

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

Ze względu na rangę problemu regularnie pojawiają się publikacje przedstawiane jako jego rozwiązanie, lecz zestawienia takich prób traktują je jako niezweryfikowane albo obalone, a żaden dowód nie został przyjęty przez środowisko.

Bariery dowodowe

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

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.

Charakterystyki logiczne

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

Zobacz też

Przypisy

  1. 1 2 Explained: P vs. NP [online], MIT News, 29 października 2009 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-13] (ang.).
  2. 1 2 3 4 5 Stephen Cook, The P Versus NP Problem, Clay Mathematics Institute, kwiecień 2000 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-01] (ang.).
  3. 1 2 3 4 5 Lance Fortnow, The status of the P versus NP problem, „Communications of the ACM”, 52 (9), 2009, s. 78–86, DOI: 10.1145/1562164.1562186 (ang.).
  4. 1 2 Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, s. 2–3, ISBN 978-0-521-42426-4 (ang.).
  5. ↑ John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, wyd. 3, Pearson/Addison Wesley, 2006, ISBN 978-0-321-45536-9 (ang.).
  6. 1 2 3 4 Michael Sipser, Introduction to the Theory of Computation, wyd. 3, Cengage Learning, 2013, ISBN 978-1-133-18779-0 (ang.).
  7. 1 2 The complexity of theorem-proving procedures, [w:] Stephen A. Cook, Proceedings of the Third Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 1971, s. 151–158, DOI: 10.1145/800157.805047, ISBN 978-1-4503-7464-4 (ang.).
  8. ↑ Russell Impagliazzo, Ramamohan Paturi, Francis Zane, Which Problems Have Strongly Exponential Complexity?, „Journal of Computer and System Sciences”, 63 (4), 2001, s. 512–530, DOI: 10.1006/jcss.2001.1774 [dostęp 2026-05-09] [zarchiwizowane z adresu 2024-04-16] (ang.).
  9. ↑ Takayuki Yato, Takahiro Seta, Complexity and Completeness of Finding Another Solution and Its Application to Puzzles, „IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences”, E86-A (5), 2003, s. 1052–1060 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-17] (ang.).
  10. ↑ Charles J. Colbourn, The complexity of completing partial Latin squares, „Discrete Applied Mathematics”, 8 (1), 1984, s. 25–30, DOI: 10.1016/0166-218X(84)90075-1 (ang.).
  11. ↑ Letters from John Nash, National Security Agency, 26 kwietnia 2012 [dostęp 2026-05-09] [zarchiwizowane z adresu 2021-09-18] (ang.).
  12. ↑ Juris Hartmanis, Gödel, von Neumann, and the P = NP problem, „Bulletin of the European Association for Theoretical Computer Science”, 38, 1989, s. 101–107 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-19] (ang.).
  13. ↑ L.A. Levin, Универсальные задачи перебора, „Проблемы передачи информации”, 9 (3), 1973, s. 115–116 (ros.).
  14. ↑ Reducibility among combinatorial problems, [w:] Richard M. Karp, Complexity of Computer Computations, 1972, s. 85–103, DOI: 10.1007/978-1-4684-2001-2_9 (ang.).
  15. 1 2 3 Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979, ISBN 978-0-7167-1045-5 (ang.).
  16. 1 2 Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994, ISBN 978-0-201-53082-7 (ang.).
  17. ↑ Richard E. Ladner, On the structure of polynomial time reducibility, „Journal of the ACM”, 22 (1), 1975, s. 151–171, DOI: 10.1145/321864.321877 (ang.).
  18. 1 2 Lance Fortnow, Complexity Class of the Week: Factoring [online], 13 września 2002 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-06-09] (ang.).
  19. ↑ Uwe Schöning, Graph isomorphism is in the low hierarchy, „Journal of Computer and System Sciences”, 37 (3), 1988, s. 312–323, DOI: 10.1016/0022-0000(88)90010-4 (ang.).
  20. ↑ Group, graphs, algorithms: the graph isomorphism problem, [w:] László Babai, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures, World Scientific, 2018, s. 3319–3336, MR 3966534 (ang.).
  21. ↑ Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, „SIAM Journal on Computing”, 26 (5), 1997, s. 1484–1509, DOI: 10.1137/S0097539795293172 (ang.).
  22. ↑ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P, „Annals of Mathematics”, 160 (2), 2004, s. 781–793, DOI: 10.4007/annals.2004.160.781 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-04-24] (ang.).
  23. ↑ Aviezri S. Fraenkel, David Lichtenstein, Computing a perfect strategy for n × n chess requires time exponential in n, „Journal of Combinatorial Theory, Series A”, 31 (2), 1981, s. 199–214, DOI: 10.1016/0097-3165(81)90016-9 (ang.).
  24. ↑ Michael J. Fischer, Michael O. Rabin, Super-Exponential Complexity of Presburger Arithmetic, „Proceedings of the SIAM-AMS Symposium in Applied Mathematics”, 7, 1974, s. 27–41 [dostęp 2026-05-09] [zarchiwizowane z adresu 2006-09-15] (ang.).
  25. ↑ Leslie G. Valiant, The complexity of enumeration and reliability problems, „SIAM Journal on Computing”, 8 (3), 1979, s. 410–421, DOI: 10.1137/0208032 (ang.).
  26. ↑ Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, „SIAM Journal on Computing”, 20 (5), 1991, s. 865–877, DOI: 10.1137/0220053 (ang.).
  27. ↑ Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy, Proof verification and the hardness of approximation problems, „Journal of the ACM”, 45 (3), 1998, s. 501–555, DOI: 10.1145/278298.278306 (ang.).
  28. ↑ Ethan Bernstein, Umesh Vazirani, Quantum complexity theory, „SIAM Journal on Computing”, 26 (5), 1997, s. 1411–1473, DOI: 10.1137/S0097539796300921 (ang.).
  29. ↑ Rodney G. Downey, Michael R. Fellows, Parameterized Complexity, Springer, 1999, ISBN 978-0-387-94883-6 (ang.).
  30. ↑ Completeness classes in algebra, [w:] Leslie G. Valiant, Proceedings of the 11th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 1979, s. 249–261, DOI: 10.1145/800135.804419 (ang.).
  31. ↑ How good is the simplex algorithm?, [w:] Victor Klee, George J. Minty, Inequalities III, Academic Press, 1972, s. 159–175 (ang.).
  32. 1 2 Daniel A. Spielman, Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, „Journal of the ACM”, 51 (3), 2004, s. 385–463, DOI: 10.1145/990308.990310, ISSN 0004-5411 (ang.).
  33. ↑ A computational view of interior point methods, [w:] Jacek Gondzio, Tamás Terlaky, Advances in Linear and Integer Programming, Oxford University Press, 1996, s. 103–144 (ang.).
  34. ↑ Russell Impagliazzo, A personal view of average-case complexity [online], 10th Annual Structure in Complexity Theory Conference, 1995 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-19] (ang.).
  35. 1 2 Steve Smale, Mathematical Problems for the Next Century. Second Version [online], City University of Hong Kong, 7 sierpnia 1998 [zarchiwizowane z adresu 2015-05-05] (ang.).
  36. ↑ Bonnie Berger, Tom Leighton, Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete, „Journal of Computational Biology”, 5 (1), 1998, s. 27–40, DOI: 10.1089/cmb.1998.5.27, PMID: 9541869 (ang.).
  37. ↑ David S. Johnson, A Brief History of NP-Completeness, 1954–2012, „Documenta Mathematica”, 2012, s. 359–376 [dostęp 2026-05-09] [zarchiwizowane z adresu 2023-06-07] (ang.).
  38. ↑ L.R. Foulds, The Heuristic Problem-Solving Approach, „Journal of the Operational Research Society”, 34 (10), 1983, s. 927–934, DOI: 10.2307/2580891, JSTOR: 2580891 (ang.).
  39. ↑ William I. Gasarch, Guest Column: The Third P =? NP Poll [online], SIGACT News, 2019 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-03-04] (ang.).
  40. ↑ Gerhard J. Woeginger, The P-versus-NP page [online] [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-18] (ang.).
  41. ↑ Theodore Baker, John Gill, Robert Solovay, Relativizations of the P =? NP Question, „SIAM Journal on Computing”, 4 (4), 1975, s. 431–442, DOI: 10.1137/0204037 (ang.).
  42. ↑ Alexander A. Razborov, Steven Rudich, Natural proofs, „Journal of Computer and System Sciences”, 55 (1), 1997, s. 24–35, DOI: 10.1006/jcss.1997.1494 (ang.).
  43. ↑ Scott Aaronson, Avi Wigderson, Algebrization: A New Barrier in Complexity Theory, „Proceedings of the 40th Annual ACM Symposium on Theory of Computing”, 2008, s. 731–740, DOI: 10.1145/1374376.1374481 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-19] (ang.).
  44. ↑ Shai Ben-David, Shai Halevi, On the independence of P versus NP, Technion, 1992 [dostęp 2026-05-09] [zarchiwizowane z adresu 2012-03-02] (ang.).
  45. ↑ Scott Aaronson, Is P Versus NP Formally Independent?, „Bulletin of the European Association for Theoretical Computer Science”, 81, październik 2003 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-04-09] (ang.).
  46. ↑ Ronald Fagin, Generalized first-order spectra and polynomial-time recognizable sets, „SIAM-AMS Proceedings”, 7, 1974, s. 43–73 [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-19] (ang.).
  47. ↑ Neil Immerman, Languages that capture complexity classes, „SIAM Journal on Computing”, 16 (4), 1987, s. 760–778, DOI: 10.1137/0216051 (ang.).
  48. ↑ Elvira Mayordomo, P versus NP, „Monografías de la Real Academia de Ciencias de Zaragoza”, 26, 2004, s. 57–68 [dostęp 2026-05-09] [zarchiwizowane z adresu 2012-02-16] (ang.).

Bibliografia