Co to jest NP-zupełny w informatyce?

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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.

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.

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.