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 (ETH), sformułowana przez Russella Impagliazza i Ramamohana Paturiego. Według niej dla k⩾3 problem k-SAT wymaga czasu wykładniczego, czyli nie da się go rozwiązać w czasie 2δn dla dostatecznie małych δ>0, gdzie n to liczba 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 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 wykazał NP-zupełność 21 ważnych problemów i jako pierwszy pokazał szerokie zastosowanie tego pojęcia.

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. 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 jednak, że NP ≠ co-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 n i k istnieje dzielnik d liczby n taki, że 1<d<k. Problem ten należy do NP i co-NP, a nawet do klas UP i co-UP. 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, ogłoszonemu w 2002 i opublikowanemu w 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.

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 algebraicznej teorii złożoności podobną rolę odgrywa 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. Metoda sympleks jest w praktyce bardzo skuteczna, lecz specjalnie skonstruowane przykłady pokazały, że w najgorszym przypadku działa bardzo źle. 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ń 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

Jeśli, jak przypuszcza większość badaczy, P ≠ NP, nie istnieje ogólny algorytm, który zawsze poprawnie i dokładnie rozwiązywałby problem NP-zupełny. Stosuje się wtedy m.in. przeszukiwanie wyczerpujące, złożoność parametryzowaną, algorytmy przybliżone i heurystyki. Rozwój metod heurystycznych, które dają dobre rozwiązania, choć bez gwarancji ich optymalności, motywowała właśnie teoria NP-zupełności.

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 określał swoje ankiety jako obiektywny zapis subiektywnych opinii. Stephen Cook zwracał uwagę, że ze względu na znaczenie tych problemów dla przemysłu ogromna liczba programistów i inżynierów przez 30 lat bezskutecznie szukała efektywnych algorytmów dla problemów NP-zupełnych. Lance Fortnow opisywał z kolei wiele podejść, którymi bezskutecznie próbowano dowieść, że P ≠ NP.

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. Shai Ben-David i Shai Halevi wykazali, że dopóki nie zostaną użyte nowe metody teorii dowodu, wykazanie niezależności P ≠ NP od arytmetyki Peana oznaczałoby istnienie prawie wielomianowego algorytmu rozstrzygającego SAT.

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.

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 6 7 8 9 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 6 7 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. Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN 978-0-521-42426-4 (ang.).
    1. ↑ s. 26–27
    2. ↑ s. 39, 41
    3. ↑ s. 41, 55
    4. ↑ s. 45
    5. ↑ s. 45, 62
    6. ↑ s. 62
    7. 1 2 s. 42
    8. ↑ s. 56, 97
    9. ↑ s. 56
    10. ↑ s. 40, 71
    11. ↑ s. 97, 156
    12. ↑ s. 92
    13. ↑ s. 344
    14. ↑ s. 323, 326
    15. ↑ s. 25–27
    16. 1 2 s. 40
  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 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, On the Complexity of k-SAT, „Journal of Computer and System Sciences”, 62 (2), 2001, DOI: 10.1006/jcss.2000.1727 [dostęp 2026-10-26] [zarchiwizowane z adresu 2015-09-19] (ang.).
    1. ↑ s. 367
  9. ↑ 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.).
  10. ↑ 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.).
  11. ↑ 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.).
  12. ↑ MSc course: Foundations of Computer Science. NP-completeness of SUDOKU [online], Department of Computer Science, University of Oxford [dostęp 2026-10-26] [zarchiwizowane z adresu 2025-12-05] (ang.).
  13. ↑ Letters from John Nash, National Security Agency, 26 kwietnia 2012 [dostęp 2026-05-09] [zarchiwizowane z adresu 2021-09-18] (ang.).
  14. David S. Johnson, A Brief History of NP-Completeness, 1954–2012, „Documenta Mathematica”, 2012 [dostęp 2026-05-09] [zarchiwizowane z adresu 2023-06-07] (ang.).
    1. ↑ s. 359–361
    2. ↑ s. 362
    3. ↑ s. 359
    4. 1 2 s. 360
  15. ↑ 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.).
  16. ↑ L.A. Levin, Универсальные задачи перебора, „Проблемы передачи информации”, 9 (3), 1973, s. 115–116 (ros.).
  17. ↑ 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.).
  18. 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.).
  19. ↑ Christos H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994, ISBN 978-0-201-53082-7 (ang.).
  20. ↑ 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.).
  21. 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.).
  22. ↑ 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.).
  23. ↑ 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.).
  24. ↑ László Babai, Graph Isomorphism in Quasipolynomial Time, „arXiv”, 11 grudnia 2015, arXiv:1512.03547 (ang.).
  25. ↑ 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.).
  26. ↑ 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.).
  27. ↑ 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.).
  28. ↑ 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.).
  29. ↑ 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.).
  30. ↑ 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.).
  31. ↑ 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.).
  32. ↑ Ethan Bernstein, Umesh Vazirani, Quantum complexity theory, „SIAM Journal on Computing”, 26 (5), 1997, s. 1411–1473, DOI: 10.1137/S0097539796300921 (ang.).
  33. ↑ 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.).
  34. ↑ How good is the simplex algorithm?, [w:] Victor Klee, George J. Minty, Inequalities III, Academic Press, 1972, s. 159–175 (ang.).
  35. Daniel A. Spielman, Shang-Hua Teng, Smoothed Analysis of Algorithms, „arXiv”, 1 grudnia 2002, arXiv:math/0212413 (ang.).
    1. ↑ s. 598
  36. ↑ 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.).
  37. ↑ 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.).
  38. 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.).
  39. ↑ 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.).
  40. ↑ 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.).
  41. ↑ 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.).
  42. ↑ Gerhard J. Woeginger, The P-versus-NP page [online] [dostęp 2026-05-09] [zarchiwizowane z adresu 2026-05-18] (ang.).
  43. ↑ 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.).
  44. 1 2 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.).
  45. ↑ 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.).
  46. ↑ 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.).
  47. ↑ 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.).
  48. ↑ 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.).
  49. Neil Immerman, Languages that capture complexity classes, „SIAM Journal on Computing”, 16 (4), 1987, s. 760–778, DOI: 10.1137/0216051 (ang.).
    1. ↑ s. 763–764, 772
  50. ↑ 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