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.

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.

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

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 .

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.

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:

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

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)

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.

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

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

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

Znajdź interesującą definicję: