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 n
i m
czy istnieje liczba całkowita f
z 1 < f < m
taką, która f
dzieli n
( f
jest 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 n
i m
) oraz liczbę całkowitą f
ze 1 < f < m
i twierdzą, że f
jest 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 X
w NP, dla których możliwe jest zmniejszenie jakikolwiek inny problem NP Y
, aby X
w czasie wielomianowym.
Intuicyjnie oznacza to, że możemy Y
szybko rozwiązać, jeśli wiemy, jak X
szybko rozwiązać . Dokładnie, Y
sprowadza się X
, czy istnieje algorytm wielomianowy czasu f
do przekształcania instancji y
o Y
do wystąpień x = f(y)
o X
w czasie wielomianowym, o tej własności, że odpowiedź y
brzmi 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_vij
jest 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 X
jest trudny w NP, jeśli występuje problem NP-zupełny Y
, który Y
można zredukować X
w 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 P
i danych wejściowych I
zostanie 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.
I
na tematn
zmiennych, wypróbuj wszystkie2^n
moż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, gdyI
jest 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.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).
Uwagi
Yes
lubNo
wpisy: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).
źródło
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
n
composite”:n
jest liczbą całkowitą} lub EULERPATH = {„Czy wykresG
ma ścieżkę Eulera?”:G
Jest 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 .
źródło
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.
źródło
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:
źródło
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”.
źródło
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)
źródło
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.
źródło
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ę.
źródło
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:
źródło
Znajdź interesującą definicję:
źródło