Co to jest NP-zupełny w informatyce?


429

Co to jest problem NP-zupełny? Dlaczego jest to tak ważny temat w informatyce?


5
Możesz być zainteresowany odpowiedziami na to pytanie: stackoverflow.com/questions/111307/...
Dan Dyer

1
Cóż, postanowiłem napisać własną odpowiedź, ponieważ nie podobał mi się sposób, w jaki została zaakceptowana odpowiedź, i umieściłem link do pytania P = NP.
grom

1
Istnieje bardzo dobry wykład arsdigita na temat matematyki dyskretnej, który wyjaśnia, czym jest problem z NP-zupełnością. Pierwsze 50 minut dotyczy głównie algebry boolowskiej. Przejdź więc od razu do początku 53 minuty, jeśli interesują Cię tylko koncepcje P, NP, NP-zupełności, boolowskiego problemu satysfakcji i redukcji.
davitenio

1
Nigdy się nie dowiemy, bo przy dużej n nigdy się nie zakończy;)
Pete Alvin

1
Bardzo lubię i naprawdę polecam sprawdzenie tego filmu: youtube.com/watch?v=YX40hbAHx3s
Maksym Ovsianikov

Odpowiedzi:


209

NP oznacza niedeterministyczny czas wielomianowy .

Oznacza to, że problem można rozwiązać w czasie wielomianowym za pomocą niedeterministycznej maszyny Turinga (takiej jak zwykła maszyna Turinga, ale także zawierającej niedeterministyczną funkcję „wyboru”). Zasadniczo rozwiązanie musi być testowane w czasie wielokrotnym. Jeśli tak jest, a znany problem NP można rozwiązać za pomocą danego problemu ze zmodyfikowanymi danymi wejściowymi (problem NP można sprowadzić do danego problemu), to problem jest NP zakończony.

Najważniejszą rzeczą do usunięcia z problemu NP-zupełnego jest to, że nie można go rozwiązać w czasie wielomianowym w żaden znany sposób. NP-Hard / NP-Complete to sposób pokazania, że ​​niektórych klas problemów nie da się rozwiązać w realistycznym czasie.

Edycja: Jak zauważyli inni, często istnieją przybliżone rozwiązania problemów NP-Complete. W tym przypadku przybliżone rozwiązanie zwykle podaje przybliżenie związane za pomocą specjalnego zapisu, który mówi nam, jak blisko jest przybliżenie.


2
„... problem NP można sprowadzić do danego problemu ...” - ważnym ograniczeniem dla redukcji jest to, że powinna być deterministycznie wielomianowa.
Rafał Dowgird

2
Notacja O () jest ogólną notacją matematyczną stosowaną wszędzie: algorytmy aproksymacji są rzeczywiście podawane z dokładnością do O () - sprawdź dowolny dokument z algorytmem aproksymacji na arxiv.org
Ying Xiao

1
Aby nieco wyjaśnić, problemy NP dotyczą niedeterministycznych maszyn Turinga. Nadal nie wiadomo, czy problem NP-zupełny można rozwiązać w czasie wielomianowym na deterministycznej maszynie Turinga.
rjzii

1
@Yuval: Żeby było jasne. To, co miałeś wcześniej, było całkowicie błędne (chyba że P = NP). Z twojego komentarza mam wrażenie, że uważasz, że obie wersje miały rację. Jeśli nie, przepraszam.

33
Ta odpowiedź jest daleka od kompletnej i zrozumiałej i nie mogę zrozumieć, dlaczego ma tak wiele pozytywnych opinii.
nbro

428

Co to jest NP ?

NP jest zbiorem wszystkich problemów decyzyjnych (pytań z odpowiedzią „tak” lub „nie”), dla których odpowiedzi „tak” można zweryfikować w czasie wielomianowym (O (n k ), gdzie n jest rozmiarem problemu, a k jest stała) przez deterministyczną maszynę Turinga . Czas wielomianowy jest czasem używany jako definicja szybkiego lub szybkiego .

Co to jest P ?

P jest zbiorem wszystkich problemów decyzyjnych, które można rozwiązać w czasie wielomianowym za pomocą deterministycznej maszyny Turinga . Ponieważ można je rozwiązać w czasie wielomianowym, można je również zweryfikować w czasie wielomianowym. Dlatego P jest podzbiorem NP.

Co to jest NP-Complete ?

Problem x, który występuje w NP, jest również w NP-Complete wtedy i tylko wtedy, gdy każdy inny problem w NP może zostać szybko (tj. W czasie wielomianowym) przekształcony w x.

Innymi słowy:

  1. x jest w NP, a
  2. Każdy problem w NP można zredukować do x

Tak więc to, co sprawia, że NP-Complete jest tak interesujące, że jeśli którykolwiek z problemów NP-Complete miałby zostać rozwiązany szybko, wszystkie problemy NP mogą być rozwiązane szybko.

Zobacz także post Co to jest „P = NP?” I dlaczego jest tak znanym pytaniem?

Co to jest NP-Hard ?

NP-Hard to problemy, które są co najmniej tak trudne, jak najtrudniejsze problemy w NP. Zauważ, że problemy NP-Complete są również trudne dla NP. Jednak nie wszystkie problemy trudne NP są NP (lub nawet problemem decyzyjnym), mimo że NPmają prefiks. To znaczy, że NP w NP-twardym nie oznacza niedeterministycznego czasu wielomianowego . Tak, jest to mylące, ale jego użycie jest zakorzenione i raczej nie ulegnie zmianie.


4
„To znaczy, że NP w NP-twardym nie oznacza, że ​​nie jest wielomianem” <- NP w NP-zupełnym (lub gdziekolwiek indziej) nie oznacza również braku wielomianu.
sepp2k

1
Dzięki sepp2k za korektę. Chciałem powiedzieć, że nie oznacza to NP (tj. Niedeterministycznego czasu wielomianu).
grom

1
Myślę, że twoja odpowiedź upraszcza tak samo lub bardziej niż inne w tym wątku. Ale wciąż jest to dla mnie bardzo trudny problem ... Chyba dlatego płacą algorytmom za duże pieniądze.
SoftwareSavant,

3
O NP: Myślę, że tak powinno być: Problem można rozwiązać za pomocą niedeterministycznej maszyny Turinga. (raczej niederterministyczny niż dermistyczny)
hqt

2
@hqt To, co napisałem, jest poprawne. Zwróć uwagę na słowo „zweryfikowane”. Masz również rację, NP można rozwiązać w czasie wielomianowym za pomocą niedeterministycznej maszyny Turinga
grom.

32

NP-Complete oznacza coś bardzo specyficznego i musisz być ostrożny, bo inaczej pomylisz się w definicji. Po pierwsze, problem NP jest problemem typu tak / nie

  1. Dla każdego wystąpienia problemu istnieje dowód czasu wielomianowego z odpowiedzią „tak”, że odpowiedź brzmi „tak” lub (równoważnie)
  2. Istnieje algorytm wielomianowy (ewentualnie wykorzystujący zmienne losowe), który ma niezerowe prawdopodobieństwo odpowiedzi „tak”, jeśli odpowiedź na wystąpienie problemu brzmi „tak” i powie „nie” w 100% przypadków, jeśli odpowiedź brzmi nie." Innymi słowy, algorytm musi mieć współczynnik fałszywie ujemny mniejszy niż 100% i nie może zawierać fałszywie dodatnich wyników.

Problem X to NP-Complete jeśli

  1. X jest w NP, i
  2. Dla każdego problemu Y w NP istnieje „redukcja” z Y do X: algorytm wielomianowy, który przekształca dowolną instancję Y w instancję X, tak że odpowiedź na instancję Y brzmi „tak”, jeśli tylko jeśli odpowiedź na instancję X brzmi „tak”.

Jeśli X jest NP-kompletny i istnieje deterministyczny algorytm wielomianowy, który może rozwiązać wszystkie instancje X poprawnie (0% fałszywie dodatnich, 0% fałszywie ujemnych), to każdy problem w NP można rozwiązać w deterministyczno-wielomianowym czas (przez redukcję do X).

Jak dotąd nikt nie wymyślił tak deterministycznego algorytmu czasu wielomianowego, ale nikt nie udowodnił, że nie istnieje (istnieje milion dolarów dla każdego, kto może to zrobić: jest to problem P = NP ). To nie znaczy, że nie możesz rozwiązać konkretnego wystąpienia problemu NP-Complete (lub NP-Hard). Oznacza to po prostu, że nie możesz mieć czegoś, co działałoby niezawodnie we wszystkich przypadkach problemu w taki sam sposób, w jaki można niezawodnie posortować listę liczb całkowitych. Być może będziesz w stanie wymyślić algorytm, który będzie działał bardzo dobrze we wszystkich praktycznych przypadkach problemu NP-Hard.


1
Nie lubię się chwalić, ale jestem dość dumny z mojego deterministycznego algorytmu czasu wielomianowego, który jak udowodniłem, nie istnieje. ;)
Kyle Cronin

20
Odkryłem naprawdę cudowny dowód na to, który ten komentarz jest zbyt wąski, aby go
zawrzeć

Warunek nr 2 jest stwierdzeniem P =? NP, a nie standardową definicją kompletności NP. Powinno być: istnieje deterministyczny algorytm wieloczasowy, który może przekształcić dowolną inną instancję NP X w instancję Y tego problemu. Odpowiedź na Y brzmi „tak” wtedy i tylko wtedy, gdy odpowiedź na X jest „tak”.
Chris Conway,

„musisz uważać, bo inaczej pomylisz się z definicją” - o czym świadczy ta odpowiedź. Ta odpowiedź jest częściowo poprawna, ale z pewnością nie powinna była zostać zaakceptowana.
programista Windows,

29

Zasadniczo problemy tego świata można sklasyfikować jako

         1) Problem nierozwiązywalny 2) Problem nienaruszalny 3) Problem NP 4) Problem P.


         1) Pierwszy nie rozwiązuje problemu. 2) Drugi to potrzebny czas wykładniczy (czyli O (2 ^ n) powyżej). 3) Trzeci nazywa się NP. 4) Czwarty to łatwy problem.


P: odnosi się do rozwiązania problemu czasu wielomianowego.

NP: odnosi się do czasu wielomianu, aby znaleźć rozwiązanie. Nie jesteśmy pewni, że nie ma rozwiązania dla czasu wielomianowego, ale po dostarczeniu rozwiązania, rozwiązanie to można zweryfikować w czasie wielomianowym.

NP Complete: odnosi się do czasu wielomianowego, wciąż jeszcze znajdujemy rozwiązanie, ale można to zweryfikować w czasie wielomianowym. Problem NPC w NP jest trudniejszym problemem, więc jeśli możemy udowodnić, że mamy P rozwiązanie problemu NPC, to problemy NP, które można znaleźć w rozwiązaniu P.

NP Hard: odnosi się do czasu wielomianowego, który jeszcze nie znalazł rozwiązania, ale na pewno nie można go zweryfikować w czasie wielomianowym. Trudny problem NP przekracza trudność NPC.


Cieszę się, że ta odpowiedź jest dość wyrazista dla całej koncepcji. Myślałem, że problemy interaktywne to problemy NP.
PeerNet

22

NP-Complete to klasa problemów.

Klasa Pskłada się z tych problemów, które można rozwiązać w czasie wielomianowym . Na przykład można je rozwiązać w O (n k ) dla pewnej stałej k, gdzie n jest rozmiarem danych wejściowych. Mówiąc najprościej, możesz napisać program, który uruchomi się w rozsądnym czasie.

Klasa NPskłada się z tych problemów, które można zweryfikować w czasie wielomianowym. To znaczy, jeśli otrzymamy potencjalne rozwiązanie, moglibyśmy sprawdzić, czy dane rozwiązanie jest poprawne w czasie wielomianowym.

Niektóre przykłady to problem logicznej satysfakcji ( SAT ) lub problem cyklu hamiltonowskiego. Istnieje wiele problemów znanych z klasy NP.

NP-Completeoznacza, że ​​problem jest co najmniej tak trudny jak każdy problem w NP.

Jest to ważne dla informatyki, ponieważ udowodniono, że każdy problem w NP można przekształcić w inny problem w NP-zupełny. Oznacza to, że rozwiązanie dowolnego problemu NP-zupełnego jest rozwiązaniem wszystkich problemów NP.

Wiele algorytmów bezpieczeństwa zależy od tego, że nie istnieją znane rozwiązania trudnych problemów NP. Na pewno miałoby to znaczący wpływ na komputery, gdyby znaleziono rozwiązanie.


To jest źle. Problem w NP można przekształcić w dowolny problem w NP-complete, a nie jakikolwiek problem w NP. To duża różnica.
David Nehme,

Ponadto „problem jest tak samo trudny jak każdy problem w NP” - prawda, ale lepsze sformułowanie byłoby „co najmniej tak samo trudne”. Ogólnie rzecz biorąc, ta odpowiedź jest bliższa niż jakakolwiek inna odpowiedź, którą widziałem, i bliższa niż niestety zaakceptowana odpowiedź.
programista Windows

Dziękuję za twoje spostrzeżenia. Zaktualizowałem odpowiedź, uwzględniając twoje poprawki.
Vincent Ramdhanie,

1
Twoja definicja NP-Complete nie jest kompletna, musisz również określić, że problemy NP-Complete są również problemami NP (i NP-trudnymi), a nie tak trudnymi jak jakiekolwiek problemy NP. Oddam głos, jeśli zdecydujesz się zmienić, powiadom mnie i usunę głos negatywny.
nbro

20

Jest to klasa problemów, w której musimy symulować każdą możliwość, aby mieć pewność, że mamy optymalne rozwiązanie.

Istnieje wiele dobrych heurystyk dla niektórych problemów z NP-Complete, ale są one w najlepszym razie tylko wykształcone.


Prawie dobrze. Problemem może być niewyczerpujące rozwiązanie, które wciąż nie ma charakteru wielomianowego.
Mark Bessey,

1
Chociaż nie jest dokładnie w porządku, jest to wystarczająco blisko do praktycznego zastosowania. Definicja pedantyczna nie jest konieczna, chociaż OP prawdopodobnie chce definicji pedantycznej. To dobre przybliżenie!
doug65536

18

Jeśli szukasz przykładu problemu NP-zupełnego, proponuję spojrzeć na 3-SAT .

Podstawową przesłanką jest to, że masz wyrażenie w normalnej formie łączącej , co jest sposobem na powiedzenie, że masz szereg wyrażeń połączonych przez OR, które muszą być prawdziwe:

(a or b) and (b or !c) and (d or !e or f) ...

Problemem 3-SAT jest znalezienie rozwiązania, które zaspokoi wyrażenie, w którym każde z wyrażeń OR ma dokładnie 3 wartości logiczne do dopasowania:

(a or !b or !c) and (!a or b or !d) and (b or !c or d) ...

Rozwiązaniem tego może być (a = T, b = T, c = F, d = F). Jednak nie znaleziono algorytmu, który rozwiązałby ten problem w ogólnym przypadku w czasie wielomianowym. Oznacza to, że najlepszym sposobem rozwiązania tego problemu jest próba zgadywania i sprawdzania brutalnej siły i wypróbowywania różnych kombinacji, aż znajdziesz taką, która działa.

Cechą szczególną problemu 3-SAT jest to, że KAŻDY problem z kompletną NP można zredukować do problemu 3-SAT. Oznacza to, że jeśli uda Ci się znaleźć algorytm wielomianowy w celu rozwiązania tego problemu, otrzymasz 1 000 000 USD , nie wspominając o szacunku i podziwie dla informatyków i matematyków na całym świecie.


Być może myli mnie inne wyjaśnienia tutaj, ale nie powinienem czytać: „ŻADNY problem NP może zostać zredukowany do problemu 3-SAT w czasie wielomianowym”. Bo czy nie to sprawia, że ​​3-SAT NP-Complete?
DubiousPusher

@DubiousPusher Nope. Odpowiedź stwierdza to poprawnie. Ten obraz wyjaśnia, co to jest stackoverflow.com/a/7367561/2686502
jayeshsolanki93

14

Szczerze mówiąc, Wikipedia może być najlepszym miejscem na znalezienie odpowiedzi na to pytanie.

Jeśli NP = P, możemy rozwiązać bardzo trudne problemy znacznie szybciej, niż myśleliśmy wcześniej. Jeśli rozwiążemy tylko jeden problem NP-Complete w czasie P (wielomianowym), wówczas można go zastosować do wszystkich innych problemów w kategorii NP-Complete.


6
„Jeśli NP = P, możemy rozwiązać bardzo trudne problemy znacznie szybciej, niż myśleliśmy wcześniej.” -- Nie. Jeśli NP = P to istnieją rozwiązania (istnieją algorytmy deterministyczne do ich rozwiązania), ale nie ma gwarancji, że kiedykolwiek dowiemy się, jakie są.
programista Windows,

Sprawiedliwy punkt. Domyślam się, że jest to dowód na to, że P = NP może być konstruktywny (np. Publikacja algorytmu wielomianowego dla 3-SAT).
Chris Conway,

10

Musimy oddzielić algorytmy i problemy. Piszemy algorytmy do rozwiązywania problemów, które skalują się w określony sposób. Chociaż jest to uproszczenie, oznaczmy algorytm literą „P”, jeśli skalowanie jest wystarczająco dobre, a „NP”, jeśli nie jest.

Dobrze jest wiedzieć rzeczy o problemach, które próbujemy rozwiązać, zamiast algorytmów, których używamy do ich rozwiązywania. Powiemy więc, że wszystkie problemy z dobrze skalowalnym algorytmem są „w P”. A te, które mają algorytm słabego skalowania są „w NP”.

Oznacza to, że wiele prostych problemów jest również „w NP”, ponieważ możemy pisać złe algorytmy, aby rozwiązać proste problemy. Dobrze byłoby wiedzieć, które problemy w NP są naprawdę trudne, ale nie chcemy po prostu powiedzieć „to te, dla których nie znaleźliśmy dobrego algorytmu”. W końcu mogę wymyślić problem (nazwij to X), który moim zdaniem wymaga super niesamowitego algorytmu. Mówię światu, że najlepszy algorytm, jaki mogłem wymyślić, aby źle rozwiązać skale X, uważam więc, że X to naprawdę trudny problem. Ale jutro może ktoś sprytniejszy ode mnie wymyśla algorytm, który rozwiązuje X i jest w P. Więc to nie jest bardzo dobra definicja trudnych problemów.

Mimo to w NP występuje wiele problemów, dla których nikt nie zna dobrego algorytmu. Więc gdybym mógł udowodnić, że X jest pewnym rodzajem problemu: taki, w którym dobry algorytm do rozwiązania X mógłby być również użyty, w jakiś sposób okrężny, do podania dobrego algorytmu dla każdego innego problemu w NP. Teraz ludzie mogą być bardziej przekonani, że X jest naprawdę trudnym problemem. I w tym przypadku nazywamy X NP-Complete.


5

Powyższe definicje kompletnych problemów NP są poprawne, ale pomyślałem, że mógłbym wypowiadać się lirycznie na temat ich filozoficznego znaczenia, ponieważ nikt jeszcze nie zajął się tym problemem.

Prawie wszystkie złożone problemy, z którymi się spotkasz, będą NP Complete. Jest w tej klasie coś bardzo fundamentalnego, co wydaje się być obliczeniowo różne od problemów, które można łatwo rozwiązać. Mają swój własny smak i nie jest tak trudno je rozpoznać. Zasadniczo oznacza to, że żaden średnio skomplikowany algorytm nie jest w stanie dokładnie rozwiązać - planowanie, optymalizacja, pakowanie, pokrycie itp.

Ale nie wszystko stracone, jeśli napotkany problem to NP Complete. Istnieje ogromna i bardzo techniczna dziedzina, w której ludzie studiują algorytmy aproksymacyjne, co daje gwarancję bycia blisko rozwiązania pełnego problemu NP. Niektóre z nich są niezwykle silnymi gwarancjami - na przykład dla 3sat można uzyskać gwarancję 7/8 za pomocą naprawdę oczywistego algorytmu. Co więcej, w rzeczywistości istnieją pewne bardzo silne heurystyki, które przodują w dawaniu świetnych odpowiedzi (ale nie ma gwarancji!) Na te problemy.

Zauważ, że dwa bardzo znane problemy - izomorfizm grafów i faktoring - nie są znane jako P ani NP.


5

Słyszałem wyjaśnienie, że: „Kompletność NP jest prawdopodobnie jednym z bardziej zagadkowych pomysłów w badaniu algorytmów.” NP oznacza „niedeterministyczny czas wielomianowy” i jest nazwą tak zwanej klasy złożoności które problemy mogą należeć. Ważną rzeczą w klasie złożoności NP jest to, że problemy w tej klasie można zweryfikowaćza pomocą algorytmu wielomianowego czasu. Jako przykład rozważ problem z liczeniem rzeczy. Załóżmy, że na stole jest kilka jabłek. Problem polega na tym, „ile jest jabłek?” Otrzymasz możliwą odpowiedź, 8. Możesz zweryfikować tę odpowiedź w czasie wielomianowym, korzystając z algorytmu liczenia jabłek. Liczenie jabłek odbywa się w czasie O (n) (to zapis Big-oh), ponieważ liczenie każdego jabłka wymaga jednego kroku. Dla n jabłek potrzebujesz n kroków. Ten problem występuje w klasie złożoności NP.

Problem jest klasyfikowany jako NP-zupełny, jeśli można wykazać, że jest on zarówno NP-twardy, jak i możliwy do zweryfikowania w czasie wielomianowym. Nie wchodząc zbyt głęboko w dyskusję na temat NP-Hard, wystarczy powiedzieć, że istnieją pewne problemy, dla których nie znaleziono rozwiązań dla czasu wielomianowego. Oznacza to, że potrzeba czegoś takiego jak n! (n czynnikowe) kroki w celu ich rozwiązania. Jeśli jednak otrzymasz rozwiązanie problemu NP-Complete, możesz to zweryfikować w czasie wielomianowym.

Klasycznym przykładem problemu NP-Complete jest problem Traveling Salesman ”.

Autor: ApoxyButt Od: http://www.everything2.com/title/NP-complete


2

Problem NP: -

  1. Problem NP to taki problem, który można rozwiązać w niedeterministycznym czasie wielomianowym.
  2. Algorytm niedeterministyczny działa w dwóch etapach.
  3. Niedeterministyczny etap zgadywania i& Niedeterministyczny etap weryfikacji.

Rodzaj problemu Np

  1. NP zakończone
  2. NP Hard

NP Pełny problem: -

1 Problem decyzyjny A nazywa się NP zupełnym, jeśli ma następujące dwie właściwości:

  1. Należy do klasy NP.
  2. Każdy inny problem w NP można przekształcić w P w czasie wielomianowym.

Some Ex: -

  • Problem z plecakiem
  • problem sumy częściowej
  • Problem pokrywający wierzchołek

Szybkie pytanie o twoje etapy ... czy etap weryfikacji nie może być deterministyczny? Problemy NP nie są weryfikowane w czasie P
Branden Keck

1

Problemy z NP-zupełnym są zbiorem problemów, do których każdy inny problem NP może zostać zredukowany w czasie wielomianowym, i którego rozwiązanie może być nadal zweryfikowane w czasie wielomianowym. Oznacza to, że każdy problem NP można przekształcić w dowolny problem NP-zupełny. - Nieformalnie problem NP-zupełny to problem NP, który jest co najmniej tak „trudny” jak każdy inny problem NP.


1

O ile rozumiem

P jest zbiorem problemów, które można rozwiązać w czasie wielomianowym za pomocą deterministycznej TM.

NP to zbiór problemów, które wymagają niedeterministycznej TM, aby można je było rozwiązać w czasie wielomianowym. Oznacza to równoległe sprawdzenie wszystkich możliwych zmiennych, przy czym każda instancja zajmuje czas wielomianowy. Jeśli problem można rozwiązać, przynajmniej jeden z tych stanów równoległych musi mieć rozwiązanie problemu. Oznacza to również, że jeśli zgadłeś o zmiennych rozwiązania, jedyne, co trzeba, to sprawdzić poprawność rozwiązania w czasie wielomianowym.

NP-Hard to zbiór, w którym problemy są co najmniej tak samo trudne jak NP. Każdy problem w NP można przekształcić w problem NP-Hard w czasie wielomianowym. Problemów tych nie da się rozwiązać w czasie wielomianowym, jeśli P nie jest równe NP. To jest, gdy najtrudniejszym problemem w NP jest rozwiązanie czasu wielomianowego, wtedy tylko problemy NP-Hard są rozwiązaniem czasu wielomianowego.

NP-Complete to zestaw skrzyżowań NP i NP-Hard. Każdy problem NP może zostać przekształcony w problem NP-Complete w czasie wielomianowym. Oznacza to, że jeśli którykolwiek z NP-Complete mógłby mieć skuteczne rozwiązanie, to każdy problem NP mógłby zostać rozwiązany z tą samą wydajnością.

Daj mi znać, jeśli popełniłem błąd.


-17

Problem NP to taki, w którym algorytm komputerowy weryfikujący rozwiązanie można utworzyć w czasie wielomianowym.

problemem NP-Complete jest NP, ale jeśli możesz go rozwiązać w czasie wielomianowym (zwanym P), wszystkie problemy NP to P.

Więc się załamuj.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.