Tekst źródłowy strony Problem NP

[[Plik:P np np-complete np-hard.svg|mały|prawo|300px|[[Diagram Eulera]] dla problemów [[Problem P|P]], NP, [[Problem NP-zupełny|NP-zupełnych]] i [[Problem NP-trudny|NP-trudnych]]. Istnienie problemów wewnątrz '''NP''', ale nie należących ani do '''P''', ani do '''NP-zupełnych''', przy założeniu, że P≠NP, zostało udowodnione przez [[Twierdzenie Ladnera|Ladnera]]<ref>R.E. Ladner, ''On the structure of polynomial time reducibility'', J.ACM, 22, 1975, s. 151–171. Corollary 1.1. [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM site].</ref>.]]

'''Problem NP''' ({{ang.|nondeterministic polynomial}}, niedeterministycznie wielomianowy) – [[problem decyzyjny (teoria obliczeń)|problem decyzyjny]], dla którego rozwiązanie można zweryfikować w [[złożoność obliczeniowa|czasie wielomianowym]]. Równoważna definicja mówi, że problem jest w klasie '''NP''', jeśli może być rozwiązany w wielomianowym czasie na [[niedeterministyczna maszyna Turinga|niedeterministycznej maszynie Turinga]].

Różnica pomiędzy [[problem P|problemami P]] i NP polega na tym, że w przypadku P '''znalezienie''' rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP '''sprawdzenie''' podanego z zewnątrz rozwiązania ma mieć taką złożoność.

Przykładowy problem:
: Czy jakikolwiek niepusty [[podzbiór]] zadanego zbioru (np. <math>\{-2,6,-3,72,10,-11\}</math>) sumuje się do zera?

Trudno znaleźć rozwiązanie tego zagadnienia w czasie wielomianowym. Nasuwający się algorytm sprawdzenia wszystkich możliwych podzbiorów ma złożoność wykładniczą ze względu na liczebność zbioru. Nie wiadomo zatem, czy problem ten jest klasy P. Na pewno natomiast uzyskawszy z zewnątrz kandydata na rozwiązanie (np. <math>\{-2,6,-3,10,-11\}</math>) możemy w liniowym (a zatem wielomianowym) czasie sprawdzić, czy sumuje się do zera. Jest to zatem problem NP.

W szczególności wszystkie problemy [[problem P|klasy '''P''']] są '''NP''', ponieważ można je sprawdzić w czasie [[wielomian]]owym. Innymi słowy, [[problem P|klasa '''P''']] zawiera się nieostro w '''NP''' <math>(P \subseteq NP).</math> Nie wiadomo natomiast, czy istnieje problem '''NP''', który nie jest w klasie '''P''' (czyli, czy '''P''' różni się od '''NP''' lub inaczej <math>P\neq NP</math> albo <math>P\subset NP</math>)<ref name="epwn">{{Encyklopedia PWN | id = 3911899 | tytuł = hipoteza P ≠ NP | data dostępu = 2023-09-15 }}</ref>. Jest to jeden z [[Problemy milenijne|problemów milenijnych]].

== Prognozy na rozwiązanie ==
Podejmowano kilka prób oszacowania, kiedy ten problem może być rozstrzygnięty:
* W 2000 roku Buss przewidywał, że <math>P\neq NP</math> zostanie potwierdzone w ciągu 20 lat<ref>{{Cytuj | url=http://arxiv.org/pdf/cs/0205003.pdf | tytuł=arXiv:cs/0205003v1 [cs.LO&#93; 3 May 2002<!-- Tytuł wygenerowany przez bota --> | opublikowany=org/pdf/cs/0205003.pdf | data dostępu=2024-04-25}}</ref>.
* W 2001<ref name="cs.umd.edu">http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf</ref> roku 40 spośród 97 ekspertów było przekonanych, że problem ten zostanie rozwiązany do 2039 roku, a 57, że do roku 2070<ref>http://www.cs.umd.edu/~gasarch/papers/poll.pdf</ref>.
* Według New Scientist z 2010 roku istnieje 50% szans na rozwiązanie problemu <math>P=NP</math> przed 2024 rokiem, gdyż 9 spośród 18 badanych hipotez udowodniono, zanim upłynęły 54 lata od ich postawienia<ref>[http://www.newscientist.com/article/mg20827923.700#.VMEnZEeG98E 2011 preview: Million-dollar mathematics problem | New Scientist<!-- Tytuł wygenerowany przez bota -->].</ref>.
* Zgodnie z ankietą z 2011 roku wśród 152 ekspertów 53% z nich uważa, iż problem zostanie rozwiązany przed 2100 rokiem, a 41%, że po nim<ref name="cs.umd.edu" />.
* W 2012 roku analiza 144 hipotez matematycznych (w tym tych nieudowodnionych) uwzględniająca wzrost liczby matematyków oraz coraz lepszy przepływ wiedzy pomiędzy nimi wykazała, że szansa na rozwiązanie problemu <math>P=NP</math> przed 2024 rokiem to 41%<ref>http://arxiv.org/ftp/arxiv/papers/1202/1202.3936.pdf</ref>.

== Definicja formalna ==
[[Klasa złożoności]] '''NP''' może być zdefiniowana w kategorii klas '''[[NTIME|NTIME(f(n))]]''' w następujący sposób:
: <math>\text{NP} = \bigcup_{k\in\mathbb{N}} \text{NTIME}(n^k).</math>

Alternatywnie, klasę '''NP''' można zdefiniować w kontekście [[Maszyna Turinga|deterministycznych maszyn Turinga]]. Powiemy, że język {{Mvar|L}} należy do '''NP''' wtedy i tylko wtedy, gdy istnieją wielomiany {{Mvar|p}} i {{Mvar|q}}, oraz deterministyczna maszyna Turinga {{Mvar|M}}, taka że:
* dla dowolnych {{Mvar|x}} i {{Mvar|y}}, maszyna {{Mvar|M}}, mając podaną na wejściu parę ({{Mvar|x}}, {{Mvar|y}}), kończy działanie w nie więcej niż {{Mvar|p}}({{Mvar|x}}) krokach,
* dla dowolnego {{Mvar|x}} należącego do {{Mvar|L}}, istnieje słowo {{Mvar|y}} długości nie większej niż {{Mvar|q}}({{Mvar|x}}), takie że maszyna {{Mvar|M}} akceptuje słowo wejściowe ({{Mvar|x}}, {{Mvar|y}}),
* dla dowolnego {{Mvar|x}} nienależącego do {{Mvar|L}} oraz dowolnego {{Mvar|y}} o długości nie większej niż {{Mvar|q}}({{Mvar|x}}), maszyna {{Mvar|M}} odrzuca słowo wejściowe ({{Mvar|x}}, {{Mvar|y}}).

== Wprowadzenie ==
Wiele naturalnych problemów [[Algorytmika|algorytmicznych]] znajduje się w [[Klasa złożoności|klasie złożoności]] '''NP'''.
W szczególności, [[Problem decyzyjny|decyzyjne]] wersje wielu interesujących [[Problem przeszukiwania|problemów przeszukiwania]] oraz [[Problem optymalizacyjny|problemów optymalizacyjnych]] należą do '''NP'''.

=== Definicja bazująca na weryfikatorach ===
W celu wyjaśnienia definicji klasy '''NP''' bazującej na weryfikatorach przeanalizujemy [[problem sumy podzbioru]]:

: ''Mając dany skończony zbiór składający się wyłącznie z [[liczby całkowite|liczb całkowitych]] (na przykład {−7, −3, −2, 5, 8}), rozstrzygnąć, czy istnieje taki jego niepusty podzbiór, którego elementy sumują się do zera (w naszym przykładzie odpowiedź jest pozytywna, gdyż podzbiorowi {-3, -2, 5} odpowiada suma {{nowrap|(−3) + (−2) + 5 {{=}} 0}}).''

Moglibyśmy zaproponować algorytm rozwiązujący powyższy problem, a bazujący na sprawdzaniu wszystkich możliwych podzbiorów. Niestety, liczba podzbiorów, a tym samym czas obliczeń, rośnie wykładniczo w stosunku do rozmiaru podanego zbioru. Zauważmy jednak, że mając podany pewien podzbiór, możemy łatwo sprawdzić, czy suma jego elementów wynosi zero. Jeśli tak jest, mówimy, że dany zbiór jest ''świadkiem'' faktu, że odpowiedź na zadany problem jest pozytywna. Algorytm sprawdzający, czy elementy zadanego zbioru sumują się do zera, nazywamy natomiast ''weryfikatorem''.

Bardziej ogólnie, mówimy, że problem obliczeniowy należy do '''NP''', jeśli istnieje dla niego weryfikator {{Mvar|V}}. Mając dowolny egzemplarz {{Mvar|I}} problemu {{Mvar|P}}, dla którego odpowiedź jest pozytywna, musi istnieć świadek {{Mvar|S}}, taki że {{Mvar|V}} akceptuje słowo wejściowe ({{Mvar|I}}, {{Mvar|S}}) w czasie wielomianowym. Co więcej, jeśli odpowiedź na {{Mvar|I}} jest negatywna, weryfikator {{Mvar|V}} odrzuci słowo ({{Mvar|I}}, {{Mvar|S}}) dla wszystkich możliwych {{Mvar|S}}. Zauważ, że weryfikator może odrzucić wejście nawet, gdy odpowiedź jest pozytywna, jeśli tylko {{Mvar|S}} nie jest poprawnym świadkiem. Dla przykładu, w przypadku problemu sumy podzbioru, jeśli istnieje podzbiór, którego elementy sumują się do zera, ale jako świadek {{Mvar|S}} wybrany zostanie inny podzbiór, dla którego nie jest to prawdą, weryfikator odrzuci słowo wejściowe. Jeśli jednak nie istnieje podzbiór o zerowej sumie, weryfikator będzie odrzucał wejście niezależnie od wyboru świadka. Ponadto w przypadku tego problemu, weryfikator działa w czasie wielomianowym (potrzeba jedynie sprawdzić, czy {{Mvar|S}} faktycznie jest podzbiorem {{Mvar|I}} oraz czy suma jego elementów jest zerowa), a zatem problem sumy podzbioru należy do klasy '''NP'''.

Dopełnienie przytoczonego problemu obliczeniowego może zostać sformułowane w następujący sposób:
: ''Mając dany skończony zbiór liczb całkowitych, rozstrzygnąć, czy dowolny jego niepusty podzbiór ma niezerową sumę.''
Definicja bazująca na weryfikatorach nie wymaga istnienia żadnego łatwego do zweryfikowania świadka dla odpowiedzi negatywnej. Klasę problemów obliczeniowych z takimi świadkami nazywamy '''[[Klasa Co-NP|co-NP]]'''. Problemem otwartym jest czy dla dowolnego problemu obliczeniowego w klasie '''NP''' istnieją świadkowie odpowiedzi negatywnych, a zatem czy zawierają się one w '''co-NP'''.

=== Definicja bazująca na maszynach Turinga ===
Następująca definicja jest równoważna definicji bazującej na weryfikatorach:
: Klasa złożoności '''NP''' jest zbiorem [[Problem decyzyjny|problemów decyzyjnych]] rozpoznawanych przez [[Niedeterministyczna maszyna Turinga|niedeterministyczną maszynę Turinga]] działającą w [[Algorytm wielomianowy|czasie wielomianowym]] (oznacza to, że jeśli słowo należy do języka to istnieje przebieg akceptujący – klasa '''[[Klasa Co-NP|co-NP]]''' jest zdefiniowana analogicznie w kategorii ścieżek odrzucających).
Równoważność powyższej definicji z tą bazującą na weryfikatorach opiera się na fakcie, że niedeterministyczna maszyna Turinga można rozwiązać problem z klasy '''NP''' w czasie wielomianowym poprzez niedeterministyczny wybór świadka oraz symulację na nim weryfikatora. Z drugiej strony, jeśli istnieje niedeterministyczna maszyna {{Mvar|M}} rozwiązująca pewien problem z '''NP''', możemy łatwo skonstruować weryfikator dla tego problemu. Będzie on w deterministyczny sposób symulował pewien przebieg maszyny {{Mvar|M}}, korzystając ze świadka za każdym razem, gdy należy dokonać niedeterministycznego wyboru.

=== Przykłady ===
Poniżej znajduje się niekompletna lista problemów znajdujących się w klasie '''NP'''.

* Wszystkie problemy z klasy '''[[Problem P|P]]''' (Dla dowolnego świadka weryfikator może go zignorować i rozwiązać problem w czasie wielomianowym. Alternatywnie, deterministyczna maszyna Turinga jest jednocześnie przypadkiem szczególnym maszyny niedeterministycznej.)
* Wersja decyzyjna [[Rozkład na czynniki|problemu faktoryzacji]]: mając dane liczby naturalne {{Mvar|n}} oraz {{Mvar|k}}, rozstrzygnąć, czy istnieje dzielnik {{Mvar|d}} liczby {{Mvar|n}}, taki że 1 &lt; {{Mvar|d}} &lt; {{Mvar|k}}.
* Problem [[Izomorfizm grafów|izomorfizmu grafów]].
* Wszystkie problemy '''[[Problem NP-zupełny|NP-zupełne]]''', między innymi:
** [[Problem komiwojażera]], polegający na znalezieniu cyklu o minimalnej sumie wag, zawierającego wszystkie wierzchołki grafu
** [[Problem spełnialności]]: mając daną [[formuła logiczna|formułę logiczną]], rozstrzygnąć, czy istnieje takie wartościowanie [[zmienna zdaniowa|zmiennych zdaniowych]], żeby formuła była prawdziwa.

== Własności ==
Klasa '''NP''' jest zamknięta na:
* [[Suma zbiorów|sumę zbiorów]]
* [[Część wspólna|przecięcie zbiorów]]
* [[Konkatenacja|konkatenację]]
* [[domknięcie Kleene’ego]]
* odwrotność

Nie jest wiadome, czy '''NP''' jest zamknięte na [[Dopełnienie zbioru|dopełnienie]] (jest to tak zwany [[problem NP vs. co-NP]]).

== Dlaczego niektóre problemy NP są trudne ==
Ponieważ w klasie tej znajduje się wiele istotnych problemów, podjęte zostały intensywne prace nad znalezieniem algorytmów działających w czasie wielomianowym rozwiązujących problemy '''NP'''. Niemniej jednak, w klasie '''NP''' wciąż pozostało wiele problemów, dla których nie udało się opracować takich algorytmów i wydają się one wymagać [[Złożoność superwielomianowa|superwielomianowego]] czasu obliczeń. Zagadnienie, czy wszystkie takie problemy da się rozwiązać w czasie wielomianowym jest jednym z najważniejszych pytań [[Informatyka|informatyki]] (jest to tak zwany [[problem P vs NP]]).

Ważnym dla tego problemu pojęciem jest klasa problemów '''[[Problem NP-zupełny|NP-zupełnych]]''', która jest podzbiorem '''NP''' i może być nieformalnie rozumiana jako zbiór „najtrudniejszych” problemów '''NP'''. Jeśli istnieje wielomianowy algorytm rozwiązujący pewien problem '''NP-zupełny''', to dowolny problem '''NP''' można rozwiązać w czasie wielomianowym. W związku z tym, oraz z powodu wielu przeprowadzonych badań skupiających się na znalezieniu wielomianowych rozwiązań dla problemów '''NP-zupełnych''', które zakończyły się niepowodzeniem, jeśli dla danego problemu zostanie udowodnione, że jest on '''NP-zupełny''', to jest wielce prawdopodobne, że nie istnieje dla niego algorytm wielomianowy.

Tym niemniej, dla niektórych problemów '''NP''' istnieją algorytmy wielomianowe, które dają rozwiązanie nieoptymalne, ale często wystarczająco dobre. Ponadto rzeczywiste przypadki niektórych problemów są łatwiejsze do rozwiązania niż ich teoretyczne odpowiedniki.

== Równoważność definicji ==
Obie definicje klasy złożoności obliczeniowej '''NP''' – ta przedstawiająca ją jako zbiór [[Język formalny|języków]] akceptowanych przez niedeterministyczne maszyny Turinga w czasie wielomianowej, oraz ta mówiąca, że są to problemy o rozwiązaniach weryfikowalnych przez deterministyczną maszynę Turinga – są sobie równoważne.

W celu udowodnienia tego faktu przyjmijmy najpierw, że mamy deterministyczny weryfikator. Niedeterministyczna maszyna Turinga może w prosty sposób zasymulować działanie tego weryfikatora na słowie wejściowym oraz wszystkich możliwych świadkach. Wymaga to tylko wielomianowo wiele kroków, ponieważ wybór kolejnego znaku świadka odbywa się w sposób niedeterministyczny, a długość świadka musi być ograniczona z góry przez wielomian względem długości słowa wejściowego. Jeśli dla danego słowa wejściowego istnieje jakikolwiek poprawny świadek, będzie również istniał akceptujący przebieg niedeterministycznej maszyny. Natomiast jeśli świadek nie istnieje, to znaczy, że wszystkie przebiegi maszyny odrzucą słowo wejściowe. Z poprawności weryfikatora wiemy jednak, że słowo takie nie należy do rozważanego języka.

Z drugiej strony, przypuśćmy, że mamy daną niedeterministyczną maszynę Turinga {{Mvar|M}} akceptującą język {{Mvar|L}} w czasie wielomianowym. W każdym z wielomianowo wielu kroków drzewo obliczeń maszyny {{Mvar|M}} może rozgałęziać się na co najwyżej skończoną liczbę różnych przebiegów. Dla danego słowa wejściowego możemy zatem zakodować przebiegi maszyny przy użyciu słów o długości ograniczonej wielomianem względem długości wejścia. Weryfikator może zatem dla podanej na wejściu pary ({{Mvar|w}}, {{Mvar|s}}) symulować przebieg {{Mvar|s}} maszyny {{Mvar|M}} na słowie wejściowym {{Mvar|w}}. Jeśli każdy przebieg maszyny odrzucał {{Mvar|w}}, nie będzie istniał poprawny świadek. Jeśli natomiast maszyna akceptowała to słowo w pewnym przebiegu, to jego kodowanie będzie poprawnym świadkiem.

== Powiązania z innymi klasami złożoności ==
* <math>P \subseteq NP</math>
: Fakt ten wynika wprost z faktu, że deterministyczna maszyna Turinga jest szczególnym przypadkiem maszyny niedeterministycznej
* <math>NP \subseteq PSPACE</math>
: Aby udowodnić ten fakt, weźmy dowolną niedeterministyczną maszyną Turinga {{Mvar|M}}. Skonstruujemy deterministyczną maszynę {{Mvar|M’}} akceptującą ten sam język i działającą w wielomianowej pamięci. Maszyna {{Mvar|M’}} będzie w pętli przeglądała wszystkich możliwych świadków i uruchamiała działający w czasie wielomianowym weryfikator. Ponieważ działająca w czasie wielomianowym maszyna może zapisać tylko wielomianowo wiele bitów, będzie ona należała do [[Klasa PSPACE|klasy PSPACE]]. Również liczba bitów świadka, jaką może odczytać taka maszyna, jest ograniczona przez wielomian, a zatem możemy się ograniczyć tylko do sprawdzania świadków, których długość jest wielomianowa względem długości wejścia.
* <math>NP \subseteq EXPTIME</math>
: Dowód przebiega w ten sam sposób jak w przypadku zależności <math>NP \subseteq PSPACE,</math> gdyż przedstawiona maszyna {{Mvar|M’}} działa w czasie wielomianowym.

[[Dopełnienie zbioru|Dopełnieniem]] klasy '''NP''' nazywamy klasę '''[[Problem co-NP|co-NP]]''', zawierającą takie problemy, gdzie dla każdego słowa wejściowego o odpowiedzi negatywnej istnieje tego świadek (zwany często kontrprzykładem). Przykładowo, problem [[Test pierwszości|testu pierwszości]] jest '''co-NP''', gdyż dobrym świadkiem odpowiedzi negatywnej może być nietrywialny dzielnik zadanej na wejściu liczby.

'''NP''' jest klasą [[Problem decyzyjny|problemów decyzyjnych]]. Analogiczną klasą dla problemów funkcyjnych jest klasa złożoności [[Problem FNP|'''FNP''']].

== Inne charakteryzacje ==
W kategoriach [[Teoria złożoności opisowej|teorii złożoności opisowej]] ({{ang.|descriptive complexity theory}}), klasa '''NP''' odpowiada zbiorowi [[Język formalny|języków]] definiowalnych przez egzystencjalną [[Logika|logikę]] drugiego rzędu – w skrócie [[Europejskie Obserwatorium Południowe|ESO]] ([[twierdzenie Fagina]]).

Klasa '''NP''' może być rozumiana jako rodzaj bardzo prostego [[Interaktywny system dowodzenia|interaktywnego systemu dowodzenia]], w którym dowodzący dostarcza świadka dowodu, a weryfikator jest deterministyczną maszyną Turinga działającą w czasie wielomianowym, która sprawdza poprawność świadka. Takie rozumowanie jest poprawne, ponieważ właściwe słowo-świadek, jeśli takie istnieje, zostanie zaakceptowane przez weryfikator oraz weryfikator nie zaakceptuje wejścia, jeśli poprawny świadek nie istnieje.

Ważnym rezultatem [[Złożoność obliczeniowa|teorii złożoności obliczeniowej]] jest fakt, że '''NP''' może być określone jako klasa tych problemów, które są rozwiązywalne przez system '''[[PCP (złożoność obliczeniowa)|PCP]]''' ({{ang.|probabilistically checkable proof}}, dowód weryfikowalny probablistycznie), w którym weryfikator używa O(log {{Mvar|n}}) losowych bitów oraz korzysta tylko ze stałej liczby bitów słowa-świadka (klasa '''PCP'''(log {{Mvar|n}}, 1)). Prostszymi słowami, oznacza to, że weryfikator dla problemów '''NP''' omawiany we wcześniejszych sekcjach może być zastąpiony przez taki, który wykonuje tylko ustaloną liczbę odczytów pewnych fragmentów świadka, a następnie logarytmicznie wiele razy rzuca monetą i na podstawie tego jest w stanie określić poprawność świadka z dużym prawdopodobieństwem. Rezultat ten pozwolił udowodnić kilka faktów odnośnie do [[Algorytm aproksymacyjny|algorytmów aproksymacyjnych]].

== Przykład ==
Wersja [[Problem decyzyjny|decyzyjna]] [[Problem komiwojażera|problemu komiwojażera]] należy do klasy '''NP''' i jest sformułowana następująco:
: Mając macierz odległości pomiędzy {{Mvar|n}} miastami, rozstrzygnąć, czy istnieje trasa z pewnego ustalonego miasta początkowego odwiedzająca wszystkie pozostałe miasta i kończąca się w mieście początkowym, której całkowita długość nie przekracza {{Mvar|k}}.

Świadkiem może być oczywiście lista kolejnych miast na wynikowej trasie. Weryfikacja może przeprowadzona w czasie wielomianowym przez [[Maszyna Turinga|deterministyczną maszynę Turinga]] poprzez proste zsumowanie wartości w komórkach macierzy opowiadających odległościom między kolejnymi miastami.

Niedeterministyczna maszyna Turinga może znaleźć odpowiednią trasę w następujący sposób:

* W każdym odwiedzonym mieście w niedeterministyczny sposób odgadujemy następne miasto do odwiedzenia, dopóki wszystkie wierzchołki nie zostaną odwiedzone.
* Gdy wszystkie wierzchołki zostaną odwiedzone, sprawdzane jest, czy długość znalezionej trasy nie przekracza {{Mvar|k}}.

O niedeterministycznym wyborze można myśleć jak o sklonowaniu maszyny Turinga wraz z jej stanem, tak aby każda z maszyn sprawdziła inny możliwy przebieg. Jeśli co najmniej jedna z maszyn odnajdzie trasę krótszą niż {{Mvar|k}}, maszyna niedeterministyczna akceptuje wejście. Można również wyobrażać to sobie jako pojedynczą maszynę Turinga, która zawsze odgaduje poprawnie, które miasto należy odwiedzić jako następne tak, aby trasa nie przekracza zadanego limitu.

Poprzez [[wyszukiwanie binarne]] po przedziale możliwych sumarycznych długości tras (ograniczone przez iloczyn liczby miast {{Mvar|n}} oraz maksymalną wartość w macierzy odległości) można sprowadzić optymalizacyjną wersję problemu komiwojażera do wersji decyzyjnej.

== Zobacz też ==
* [[maszyna Turinga]]
* [[problem obliczeniowy]]
* [[problemy milenijne]]

== Przypisy ==
{{Przypisy}}

== Linki zewnętrzne ==
* Tomasz Kazana, ''[http://www.deltami.edu.pl/temat/informatyka/2016/12/27/Czemu_nikt_nie_wierzy_ze_P_NP/ Czemu nikt nie wierzy, że P=NP?]''.
* {{MathWorld | adres = NP-Problem | tytuł = NP-Problem }} [dostęp 2023-06-18].
* {{otwarty dostęp}} ''[https://encyclopediaofmath.org/wiki/NP NP]'' {{lang|en}}, Encyclopedia of Mathematics, encyclopediaofmath.org, [dostęp 2023-06-18].

{{Klasy złożoności}}
{{Problemy milenijne}}

[[Kategoria:Klasy złożoności]]