Jakie są różnice między NP, NP-Complete i NP-Hard?

1107

Jakie są różnice między NP , NP-Complete i NP-Hard ?

Jestem świadomy wielu zasobów w Internecie. Chciałbym przeczytać twoje wyjaśnienia, a powodem jest to, że mogą one różnić się od tego, co tam jest, lub jest coś, czego nie jestem świadomy.

DarthVader
źródło

Odpowiedzi:

1438

Zakładam, że szukasz definicji intuicyjnych, ponieważ definicje techniczne wymagają sporo czasu na ich zrozumienie. Przede wszystkim pamiętajmy o niezbędnej wstępnej koncepcji, aby zrozumieć te definicje.

  • Problem decyzyjny : problem z odpowiedzią tak lub nie .

Teraz zdefiniujmy te klasy złożoności .

P.

P jest klasą złożoności, która reprezentuje zestaw wszystkich problemów decyzyjnych, które można rozwiązać w czasie wielomianowym .

To znaczy, biorąc pod uwagę przypadek problemu, odpowiedź tak lub nie może zostać podjęta w czasie wielomianowym.

Przykład

Biorąc pod uwagę połączony wykres G, czy jego wierzchołki można pokolorować za pomocą dwóch kolorów, aby żadna krawędź nie była monochromatyczna?

Algorytm: zacznij od dowolnego wierzchołka, pokoloruj go na czerwono, a wszystkich sąsiadów na niebiesko i kontynuuj. Zatrzymaj się, gdy zabraknie wierzchołków lub będziesz zmuszony, aby krawędź miała oba punkty końcowe tego samego koloru.


NP

NP jest klasą złożoności, która reprezentuje zestaw wszystkich problemów decyzyjnych, dla których przypadki, w których odpowiedź brzmi „tak”, zawierają dowody, które można zweryfikować w czasie wielomianowym.

Oznacza to, że jeśli ktoś poda nam przykład problemu i certyfikat (czasem nazywany świadkiem) na odpowiedź twierdzącą, możemy sprawdzić, czy jest on poprawny w czasie wielomianowym.

Przykład

Rozkład na czynniki całkowite jest w NP. Jest to problem, który daje liczby całkowite ni mczy istnieje liczba całkowita fz 1 < f < mtaką, która fdzieli n( fjest to niewielki czynnik n)?

Jest to problem decyzyjny, ponieważ odpowiedzi są tak lub nie. Jeśli ktoś ręce nam instancję problemu (więc dłoń USA liczb całkowitych ni m) oraz liczbę całkowitą fze 1 < f < mi twierdzą, że fjest czynnikiem n(certyfikat), możemy sprawdzić odpowiedź w czasie wielomianowym wykonując podział n / f.


NP-Complete

NP-Complete jest klasa złożoności co stanowi zbiór wszystkich problemów Xw NP, dla których możliwe jest zmniejszenie jakikolwiek inny problem NP Y, aby Xw czasie wielomianowym.

Intuicyjnie oznacza to, że możemy Yszybko rozwiązać, jeśli wiemy, jak Xszybko rozwiązać . Dokładnie, Ysprowadza się X, czy istnieje algorytm wielomianowy czasu fdo przekształcania instancji yo Ydo wystąpień x = f(y)o Xw czasie wielomianowym, o tej własności, że odpowiedź ybrzmi tak, wtedy i tylko wtedy, gdy odpowiedź f(y)jest twierdząca.

Przykład

3-SAT. Jest to problem polegający na tym, że otrzymujemy koniunkcję (AND) rozłączników 3-klauzulowych (OR), wyrażenia formularza

(x_v11 OR x_v21 OR x_v31) AND 
(x_v12 OR x_v22 OR x_v32) AND 
...                       AND 
(x_v1n OR x_v2n OR x_v3n)

gdzie każda x_vijjest zmienną boolowską lub negacją zmiennej ze skończonej listy predefiniowanej (x_1, x_2, ... x_n).

Można wykazać, że każdy problem NP można zredukować do 3-SAT . Dowód jest techniczny i wymaga zastosowania technicznej definicji NP ( opartej na niedeterministycznych maszynach Turinga ). Jest to znane jako twierdzenie Cooka .

To, co sprawia, że ​​problemy związane z NP-zakończeniem są ważne, to fakt, że jeśli można znaleźć deterministyczny algorytm wielomianu czasowego do rozwiązania jednego z nich, każdy problem NP można rozwiązać w czasie wielomianowym (jednym problemem do rządzenia nimi wszystkimi).


NP-twardy

Intuicyjnie są to problemy, które są co najmniej tak trudne, jak problemy z NP-zupełnością . Zauważ, że problemy trudne NP nie muszą występować w NP i nie muszą to być problemy decyzyjne .

Dokładna definicja polega na tym, że problem Xjest trudny w NP, jeśli występuje problem NP-zupełny Y, który Ymożna zredukować Xw czasie wielomianowym .

Ale ponieważ każdy problem NP-zupełny można zredukować do dowolnego innego problemu NP-zupełnego w czasie wielomianowym, wszystkie problemy NP-zupełne można zredukować do dowolnego problemu trudnego dla NP w czasie wielomianowym. Następnie, jeśli istnieje rozwiązanie jednego trudnego problemu NP w czasie wielomianowym, istnieje rozwiązanie wszystkich problemów NP w czasie wielomianowym.

Przykład

Zatrzymanie Problem jest NP-trudny problem. Jest to problem, który przy danym programie Pi danych wejściowych Izostanie zatrzymany? Jest to problem decyzyjny, ale nie ma go w NP. Oczywiste jest, że każdy problem NP-zupełny można zredukować do tego. Jako kolejny przykład, każdy problem NP-zupełny jest NP-trudny.

Moim ulubionym problemem NP-zupełnym jest problem Saper .


P = NP

Ten jest najbardziej znanym problemem w informatyce i jednym z najważniejszych nierozstrzygniętych pytań w naukach matematycznych. W rzeczywistości Clay Institute oferuje milion dolarów na rozwiązanie problemu ( opis Stephena Cooka na stronie Clay jest całkiem dobry).

Oczywiste jest, że P jest podzbiorem NP. Pytanie otwarte dotyczy tego, czy problemy NP mają deterministyczne rozwiązania dotyczące czasu wielomianowego. Powszechnie uważa się, że nie. Oto wybitny najnowszy artykuł na temat najnowszego (i znaczenia) problemu P = NP: Status problemu P w porównaniu z NP .

Najlepsza książka na ten temat to Komputery i nienaruszalność autorstwa Garey i Johnsona.

Jason
źródło
32
@Paul Fisher: Pokażę, że SAT można zredukować do problemu zatrzymania w czasie wielomianowym. Rozważ następujący algorytm: podając jako dane wejściowe zdanie Ina temat nzmiennych, wypróbuj wszystkie 2^nmożliwe przypisania do zmiennych i zatrzymaj się, jeśli spełnisz zdanie, a w przeciwnym razie wejdź w nieskończoną pętlę. Widzimy, że ten algorytm przestaje działać tylko wtedy, gdy Ijest zadowalający. Zatem jeśli mielibyśmy algorytm wielomianowy do rozwiązania problemu zatrzymania, moglibyśmy rozwiązać SAT w czasie wielomianowym. W związku z tym problem zatrzymania jest trudny do uzyskania przez NP.
jason
6
@Jason - W ten sposób nie można zredukować rozstrzygalnego problemu do nierozstrzygalnego problemu. Problemy wymagające rozstrzygnięcia muszą skutkować ostateczną odpowiedzią „tak” lub „nie”, aby można je było uznać za rozstrzygające. Problem zatrzymania nie ma ostatecznej odpowiedzi tak lub teraz, ponieważ dowolna odpowiedź może wrzucić dowolne rozwiązanie do pętli.
rjzii,
11
@Rob: Tak, mogę. Definicja redukowalnego nie wymaga, aby problem został zredukowany do rozwiązania. Dotyczy to zarówno redukcji wielokrotnych, jak i redukcji Turinga.
jason
5
@Rob: Cóż, dobrze, jeśli chcesz to kontynuować. Po pierwsze, „Decidable” nie jest synonimem „problemu decyzyjnego”, gdy go wykorzystałeś. „Rozstrzygalne” oznacza z grubsza, że ​​istnieje „skuteczna metoda” określania odpowiedzi. „Metoda skuteczna” ma oczywiście definicję techniczną. Ponadto „rozstrzygalne” można również zdefiniować w kategoriach „funkcji obliczalnych”. Problem zatrzymania jest więc problemem decyzyjnym („Czy ten program się zatrzymuje?” To pytanie tak / nie), ale jest nierozstrzygalny; nie ma skutecznej metody określania, czy wystąpi problem zatrzymania.
jason
21
Używanie problemu zatrzymania jako „klasycznego przykładu” problemu trudnego dla NP jest niepoprawne. To tak, jakby powiedzieć: „Ocean Spokojny to klasyczny przykład akwarium ze słoną wodą”.
Michael
261

Rozglądałem się i widziałem wiele długich wyjaśnień. Oto mały wykres, który może być użyteczny do podsumowania:

Zauważ, jak trudność wzrasta od góry do dołu: dowolna NP może zostać zredukowana do NP-Complete , a dowolna NP-Complete może zostać zredukowana do NP-Hard , wszystko w czasie P (wielomianowym).

Jeśli potrafisz rozwiązać trudniejszą klasę problemu w czasie P, będzie to oznaczać, że udało Ci się rozwiązać wszystkie łatwiejsze problemy w czasie P (na przykład udowodnienie P = NP, jeśli wymyślisz jak rozwiązać dowolny problem NP-Complete w Czas P).

____________________________________________________________
| Rodzaj problemu | Weryfikowalny w czasie P | Rozwiązanie w czasie P | Rosnące trudności
___________________________________________________________ | |
| P | Tak | Tak | |
| NP | Tak | Tak lub Nie * | |
| NP-Complete | Tak | Nieznany | |
| NP-Hard | Tak lub Nie ** | Nieznany *** | |
____________________________________________________________ V

Uwagi Yeslub Nowpisy:

  • * Problem NP, który jest również P, można rozwiązać w czasie P.
  • ** Trudny problem NP, który jest także NP-Complete, można zweryfikować w czasie P.
  • *** Problemy z NP-Complete (wszystkie tworzą podzbiór NP-hard). Reszta NP nie jest trudna.

Uważam również, że ten diagram jest bardzo przydatny, gdy widzę, jak wszystkie te typy odpowiadają sobie nawzajem (zwracaj większą uwagę na lewą połowę diagramu).

Johnson Wong
źródło
Mam wątpliwości związane z twoją odpowiedzią. Zadałem to w osobnym pytaniu, ale poproszono mnie o opublikowanie go tutaj. Czy możesz mi pomóc tutaj? stackoverflow.com/questions/21005651/…
Srikanth
Nie wiadomo, czy problemy NP-zupełne można rozwiązać w czasie wielomianowym. Również problemy z NP są trudne do NP, więc niektóre problemy z NP są możliwe do zweryfikowania w czasie wielomianowym, a niektóre możliwe również do rozwiązania w czasie wielomianowym.
Falk Hüffner,
Ta tabela jest niepoprawna i wewnętrznie sprzeczna. Nawet jeśli założymy, że NP! = P, czego jeszcze nie udowodniono, nadal byłoby niepoprawne. Na przykład klasa NP-Hard obejmuje problemy z NP-Complete; dlatego twoja tabela twierdzi, że problemy NP-Complete są jednocześnie weryfikowalne w czasie wielomianowym, a nie weryfikowalne w czasie wielomianowym.
Michael
3
@ FalkHüffner Dzięki, tabela została zaktualizowana (wystąpił błąd w tłumaczeniu z diagramu Venna).
Johnson Wong
1
@PeterRaeves Wszystkie problemy z NP-zupełnym są trudne NP, z definicji: NP-complete = (NP i NP-hard). Odwrotna sytuacja nie jest prawdą: istnieją problemy (takie jak problem zatrzymania) w NP-hard, które nie są w NP-zupełne. „NP (nierozwiązywalne w czasie wielomianowym)” - nie to oznacza NP. NP to „niedeterministyczno-wielomian”. Wszystkie problemy w P są również w NP. To, czy odwrotność jest prawdziwa, jest znane.
Jim Balter,
73

To bardzo nieformalna odpowiedź na zadane pytanie.

Czy 3233 można zapisać jako iloczyn dwóch innych liczb większych niż 1? Czy jest jakiś sposób na obejście wszystkich siedmiu mostów w Królewcu bez podwójnego przejazdu? To są przykłady pytań, które mają wspólną cechę. Może nie być oczywiste, jak skutecznie ustalić odpowiedź, ale jeśli odpowiedź brzmi „tak”, to jest krótki i szybki dowód. W pierwszym przypadku nietrywialna faktoryzacja 51; w drugim trasa do przejścia po mostach (dopasowanie do ograniczeń).

Problem decyzyjny jest zbiorem pytań tak lub nie odpowiedzi, które różnią się tylko jednego parametru. Powiedzmy, że problem COMPOSITE = {„Is ncomposite”: njest liczbą całkowitą} lub EULERPATH = {„Czy wykres Gma ścieżkę Eulera?”: GJest wykresem skończonym}.

Teraz niektóre problemy decyzyjne nadają się do wydajnych, jeśli nie oczywistych algorytmów. Euler odkrył skuteczny algorytm dla problemów takich jak „Siedem mostów z Królewca” ponad 250 lat temu.

Z drugiej strony, w przypadku wielu problemów decyzyjnych nie jest oczywiste, jak uzyskać odpowiedź - ale jeśli znasz jakieś dodatkowe informacje, oczywiste jest, w jaki sposób można udowodnić, że masz właściwą odpowiedź. KOMPOZYT ​​jest taki: podział na próbę jest oczywistym algorytmem i jest powolny: aby uwzględnić 10-cyfrową liczbę, musisz wypróbować około 100 000 możliwych dzielników. Ale jeśli na przykład ktoś powiedział ci, że 61 jest dzielnikiem 3233, prosty długi podział jest skutecznym sposobem na sprawdzenie, czy są poprawne.

Klasa złożoności NP to klasa problemów decyzyjnych, w których odpowiedzi „tak” mają krótkie stwierdzenie, szybkie sprawdzenie dowodów. Jak KOMPOZYT. Ważną kwestią jest to, że ta definicja nie mówi nic o tym, jak trudny jest problem. Jeśli masz prawidłowy, skuteczny sposób rozwiązania problemu decyzyjnego, wystarczy zapisać kroki w rozwiązaniu, co jest wystarczającym dowodem.

Badania algorytmów są kontynuowane, a nowe sprytne algorytmy są tworzone przez cały czas. Problem, którego dziś nie wiesz, jak skutecznie rozwiązać, może jutro mieć skuteczne (jeśli nie oczywiste) rozwiązanie. W rzeczywistości naukowcy potrzebowali do 2002 roku znalezienia skutecznego rozwiązania dla KOMPOZYTU! Przy tych wszystkich postępach naprawdę trzeba się zastanawiać: czy chodzi o to, by krótkie dowody były tylko iluzją? Może każdy problem decyzyjny, który nadaje się do wydajnych dowodów, ma skuteczne rozwiązanie? Nikt nie wie .

Być może największy wkład w tę dziedzinę przyniósł odkrycie szczególnej klasy problemów NP. Grając z modelami obwodów do obliczeń, Stephen Cook znalazł problem decyzyjny odmiany NP, który okazał się równie trudny lub trudniejszy niż każdy inny problem NP. Skuteczne rozwiązanie problemu logicznej satysfakcji może być wykorzystane do stworzenia skutecznego rozwiązania dowolnego innego problemu w NP. Wkrótce potem Richard Karp pokazał, że wiele innych problemów decyzyjnych może służyć temu samemu celowi. Problemy te, w pewnym sensie „najtrudniejsze” problemy w NP, stały się znane jako problemy NP-zupełne .

Oczywiście NP to tylko klasa problemów decyzyjnych. Wiele problemów nie jest w naturalny sposób sformułowanych w ten sposób: „znajdź czynniki N”, „znajdź najkrótszą ścieżkę na wykresie G, która odwiedza każdy wierzchołek”, „podaj zestaw przypisań zmiennych, które sprawiają, że poniższe wyrażenie logiczne jest prawdziwe”. Chociaż można nieformalnie mówić o tym, że niektóre z takich problemów są „w NP”, technicznie nie ma to większego sensu - nie są to problemy decyzyjne. Niektóre z tych problemów mogą mieć nawet taką samą moc, jak problem NP-zupełny: skuteczne rozwiązanie tych problemów (niezwiązanych z decyzją) prowadziłoby bezpośrednio do skutecznego rozwiązania dowolnego problemu NP. Problem taki nazywa się NP-trudny .

Managu
źródło
67

P (czas wielomianowy): Jak sama nazwa wskazuje, są to problemy, które można rozwiązać w czasie wielomianowym.

NP (czas niedeterministyczno-wielomianowy): Są to problemy decyzyjne, które można zweryfikować w czasie wielomianowym. Oznacza to, że jeśli twierdzę, że istnieje rozwiązanie wielomianowe dla określonego problemu, poprosisz mnie o jego udowodnienie. Następnie dam ci dowód, który możesz łatwo zweryfikować w czasie wielomianowym. Tego rodzaju problemy nazywane są problemami NP. Zauważ, że tutaj nie mówimy o tym, czy istnieje rozwiązanie wielomianowe dla tego problemu, czy nie. Ale mówimy o weryfikacji rozwiązania danego problemu w czasie wielomianowym.

NP-Hard: Są to co najmniej tak trudne, jak najtrudniejsze problemy w NP. Jeśli potrafimy rozwiązać te problemy w czasie wielomianowym, możemy rozwiązać każdy problem NP, który może istnieć. Zauważ, że problemy te niekoniecznie są problemami NP. Oznacza to, że możemy / nie możemy zweryfikować rozwiązania tych problemów w czasie wielomianowym.

NP-Complete: Są to problemy, które są zarówno NP, jak i NP-Hard. Oznacza to, że jeśli uda nam się rozwiązać te problemy, możemy rozwiązać każdy inny problem NP, a rozwiązania tych problemów można zweryfikować w czasie wielomianowym.

Nagakishore Sidde
źródło
Więc postanowiłeś skądś skopiować definicje?
Arun Satyarth
1
Odpowiedź ma sens!
Konstantin,
2
@ArunSatyarth Skąd?
znaczenie-znaczenie
3
Najlepsza odpowiedź, ponieważ jest krótka, używa wystarczającej terminologii, ma normalne ludzkie zdania (nie trudne do odczytania, bądźmy jak najbardziej poprawne), a co zaskakujące, jedyna odpowiedź, która pisze, co oznacza N.
znaczenie-znaczenie
62

Oprócz innych świetnych odpowiedzi, oto typowy schemat, którego ludzie używają, aby pokazać różnicę między NP, NP-Complete i NP-Hard:

wprowadź opis zdjęcia tutaj

Franck Dernoncourt
źródło
1
Czy udowodniono, że istnieje problem w NP-Hard, który nie występuje w NP-Complete? Ponieważ ten obraz to sugeruje. Dziękuję Ci.
Hilder Vitor Lima Pereira
9
@VitorLima tak np. Problemy z EXPSPACE są trudne NP, ale udowodniono, że nie są NP-zupełne.
Franck Dernoncourt
2
Ok dziękuję. Znalazłem kilka referencji na ten temat. Na przykład ten: princeton.edu/~achaney/tmve/wiki100k/docs/NP-hard.html
Hilder Vitor Lima Pereira
47

Najłatwiejszym sposobem wyjaśnienia P przeciwko NP i tym podobnych bez wchodzenia w szczegóły techniczne jest porównanie „problemów słownych” z „problemami wielokrotnego wyboru”.

Kiedy próbujesz rozwiązać „problem słowny”, musisz znaleźć rozwiązanie od zera. Kiedy próbujesz rozwiązać „problemy wielokrotnego wyboru”, masz wybór: albo rozwiąż go jak „problem słowny”, albo spróbuj podłączyć każdą z udzielonych odpowiedzi i wybierz odpowiedź kandydata, która pasuje.

Często zdarza się, że „problem wielokrotnego wyboru” jest znacznie łatwiejszy niż odpowiadający mu „problem słowny”: podstawienie odpowiedzi kandydata i sprawdzenie, czy pasują, może wymagać znacznie mniej wysiłku niż znalezienie właściwej odpowiedzi od zera.

Teraz, jeśli zgodzilibyśmy się, że wysiłek, który zajmuje czas wielomianowy „łatwo”, wówczas klasa P składałaby się z „łatwych problemów słownych”, a klasa NP składałaby się z „łatwych problemów wielokrotnego wyboru”.

Istotą P przeciwko NP jest pytanie: „Czy są jakieś łatwe problemy wielokrotnego wyboru, które nie są łatwe jak problemy słowne”? To znaczy, czy istnieją problemy, dla których łatwo jest zweryfikować poprawność danej odpowiedzi, ale znalezienie odpowiedzi od podstaw jest trudne?

Teraz, gdy intuicyjnie rozumiemy, czym jest NP, musimy rzucić wyzwanie naszej intuicji. Okazuje się, że istnieją „problemy wielokrotnego wyboru”, które w pewnym sensie są najtrudniejsze ze wszystkich: gdyby ktoś znalazł rozwiązanie jednego z tych „najtrudniejszych ze wszystkich” problemów, byłby w stanie znaleźć rozwiązanie WSZYSTKIEGO Problemy NP! Kiedy Cook odkrył to 40 lat temu, było to całkowitą niespodzianką. Te „najtrudniejsze ze wszystkich” problemy są znane jako NP-trudne. Jeśli znajdziesz „rozwiązanie problemu słownego” w jednym z nich, automatycznie znajdziesz „rozwiązanie problemu słownego” dla każdego „łatwego problemu wielokrotnego wyboru”!

Wreszcie problemy NP-zupełne to te, które są jednocześnie NP i NP-trudne. Zgodnie z naszą analogią są one jednocześnie „łatwe jak problemy wielokrotnego wyboru” i „najtrudniejsze ze wszystkich jako problemy słowne”.

Michał
źródło
18

Problemy NP-zupełne to problemy, które są zarówno NP-Hard, jak i klasy złożoności NP. Dlatego, aby pokazać, że dany problem jest NP-zupełny, musisz pokazać, że problem dotyczy zarówno NP, jak i trudnej NP.

Problemy należące do klasy złożoności NP można rozwiązać niedeterministycznie w czasie wielomianowym, a możliwe rozwiązanie (tj. Certyfikat) dla problemu w NP można zweryfikować pod kątem poprawności w czasie wielomianowym.

Przykład niedeterministycznego rozwiązania problemu kliki k mógłby wyglądać następująco:

1) losowo wybierz k węzłów z wykresu

2) sprawdź, czy te węzły k tworzą klikę.

Powyższa strategia jest wielomianowa pod względem wielkości wykresu wejściowego, a zatem problem kliki k występuje w NP.

Zauważ, że wszystkie problemy rozwiązujące deterministycznie w czasie wielomianowym są również w NP.

Wykazanie, że problem jest trudny NP zwykle wiąże się z redukcją z innego problemu trudnego do NP do twojego problemu za pomocą wielomianowego mapowania czasu: http://en.wikipedia.org/wiki/Reduction_(complexity)

awesomo
źródło
Nie dlatego, że widzę w tej odpowiedzi coś, co jest niepoprawne, ale nie wiem, dlaczego zostało zaakceptowane. Tak naprawdę nie oferuje wiele do tego, o co prosi OP. Tak naprawdę nie różni się nawet od standardowych wyjaśnień tych problemów i nie ma żadnych jasnych wyjaśnień na temat tego, co powoduje te problemy w tych klasach. Nie warto głosować negatywnie, ale na pewno nie warto akceptować odpowiedzi.
San Jacinto,
18

Myślę, że możemy odpowiedzieć na to znacznie bardziej zwięźle. Odpowiedziałem na powiązane pytanie i stamtąd skopiowałem swoją odpowiedź

Ale po pierwsze, problem związany z NP jest problemem, dla którego nie możemy udowodnić, że istnieje rozwiązanie wielomianowe. Twardość NP jakiegoś „problemu-P” zwykle dowodzi się przez przekształcenie już udowodnionego problemu twardego NP w „problem-P” w czasie wielomianowym.

Aby odpowiedzieć na resztę pytania, najpierw musisz zrozumieć, które trudne problemy NP są również NP-zupełne. Jeśli trudny NP należy do zestawu NP, oznacza to, że NP jest kompletny. Problemem jest przynależność do zestawu NP

(i) problem decyzyjny,
(ii) liczba rozwiązań problemu powinna być skończona, a każde rozwiązanie powinno być wielomianowe, oraz
(iii) biorąc pod uwagę rozwiązanie długości wielomianowej, powinniśmy być w stanie powiedzieć, czy odpowiedź na problemem jest tak / nie

Teraz łatwo zauważyć, że może być wiele trudnych problemów NP, które nie należą do ustawiania NP i są trudniejsze do rozwiązania. Jako intuicyjny przykład wersja optymalizacyjna podróżnego sprzedawcy, w której musimy znaleźć rzeczywisty harmonogram, jest trudniejsza niż wersja decyzyjna podróżnego sprzedawcy, w której musimy jedynie ustalić, czy istnieje harmonogram o długości <= k.

Sushant Sharma
źródło
5

Istnieją naprawdę dobre odpowiedzi na to konkretne pytanie, więc nie ma sensu pisać własnego wyjaśnienia. Spróbuję więc wnieść doskonały zasób o różnych klasach złożoności obliczeniowej.

Dla kogoś, kto uważa, że ​​złożoność obliczeniowa dotyczy tylko P i NP, oto najbardziej wyczerpujące źródło informacji o różnych problemach złożoności obliczeniowej. Oprócz problemów zadawanych przez OP, wymieniono około 500 różnych klas problemów obliczeniowych z ładnymi opisami, a także listę podstawowych prac badawczych opisujących klasę.

Salvador Dali
źródło
3

Jak rozumiem, problem np. Trudny nie jest „trudniejszy” niż problem np. Kompletny . W rzeczywistości z definicji każdy problem z np. Kompletnością to:

  1. w NP
  2. np-trudny

wprowadź opis zdjęcia tutaj

- Wprowadzenie. na Algorytmy (3ed) autorstwa Cormen, Leiserson, Rivest i Stein, str. 1069

MrDrews
źródło
3
Twoje zrozumienie jest nieprawidłowe. Twoja definicja NP-complete jest poprawna, ale nie ma wpływu na twoje pierwsze stwierdzenie. Wszystkie problemy w NP-trudnych są co najmniej tak samo trudne jak te w NP-zupełnych; niektóre (np. problem zatrzymania, który jest nieskończenie trudny, i en.wikipedia.org/wiki/EXPSPACE ) są znacznie trudniejsze.
Jim Balter,
2

Znajdź interesującą definicję:

wprowadź opis zdjęcia tutaj

sendon1982
źródło