Klasy twarde i NP-kompletne

Problem występuje w NPC klasy, jeśli jest w NP i jest taki sam hardjak każdy problem w NP. Problem w tymNP-hard jeśli wszystkie problemy w NP można zredukować do czasu wielomianu, nawet jeśli nie jest w samym NP.

Jeśli dla któregokolwiek z tych problemów istnieje algorytm czasu wielomianowego, wszystkie problemy w NP można by rozwiązać w czasie wielomianowym. Te problemy są nazywaneNP-complete. Zjawisko NP-zupełności jest ważne zarówno ze względów teoretycznych, jak i praktycznych.

Definicja kompletności NP

Język B jest NP-complete jeśli spełnia dwa warunki

  • B jest w NP

  • Każdy A w NP jest czas wielomianowy redukowalny do B.

Jeśli język spełnia drugą właściwość, ale niekoniecznie pierwszą, język B jest znany jako NP-Hard. Nieformalnie, problem z wyszukiwaniemB jest NP-Hard jeśli istnieje NP-Complete problem A do której Turing redukuje B.

Problem w NP-Hard nie może być rozwiązany w czasie wielomianowym, dopóki P = NP. Jeśli okaże się, że problemem jest NPC, nie ma potrzeby tracić czasu na szukanie wydajnego algorytmu. Zamiast tego możemy skupić się na algorytmie aproksymacji projektu.

Problemy NP-Complete

Poniżej przedstawiono kilka problemów NP-Complete, dla których nie jest znany algorytm czasu wielomianowego.

  • Określenie, czy wykres ma cykl Hamiltona
  • Ustalenie, czy formuła boolowska jest satysfakcjonująca itp.

NP-trudne problemy

Następujące problemy są NP-trudne

  • Problem zgodności obwodu
  • Ustaw osłonę
  • Pokrywa wierzchołków
  • Problem komiwojażera

W tym kontekście omówimy teraz TSP jest NP-Complete

TSP jest NP-Complete

Problem komiwojażera składa się z komiwojażera i zbioru miast. Sprzedawca musi odwiedzić każde z miast, zaczynając od określonego i wracając do tego samego miasta. Problem polega na tym, że komiwojażer chce zminimalizować całkowitą długość podróży

Dowód

Udowodnić TSP is NP-Complete, najpierw musimy to udowodnić TSP belongs to NP. W TSP znajdujemy wycieczkę i sprawdzamy, czy trasa zawiera jeden wierzchołek. Następnie obliczany jest całkowity koszt krawędzi trasy. Na koniec sprawdzamy, czy koszt jest minimalny. Można to wykonać w czasie wielomianowym. A zatemTSP belongs to NP.

Po drugie, musimy to udowodnić TSP is NP-hard. Aby to udowodnić, jednym ze sposobów jest pokazanie tegoHamiltonian cycle ≤p TSP (jak wiemy, że problem cyklu Hamiltona jest NPkompletny).

Założyć G = (V, E) być przykładem cyklu Hamiltona.

W związku z tym konstruowana jest instancja TSP. Tworzymy pełny wykresG' = (V, E'), gdzie

$$ E ^ {'} = \ lbrace (i, j) \ colon i, j \ in V \: \: and \: i \ neq j $$

Zatem funkcja kosztu jest zdefiniowana w następujący sposób -

$$ t (i, j) = \ begin {cases} 0 & if \: (i, j) \: \ in E \\ 1 & w przeciwnym razie \ end {cases} $$

Teraz przypuśćmy, że cykl Hamiltona h istnieje w G. Oczywiste jest, że koszt każdej krawędzi wh jest 0 w G' do której należy każda krawędź E. W związku z tym,h ma koszt 0 w G'. Tak więc, jeśli wykresG ma cykl Hamiltona, a następnie wykres G' ma wycieczkę po 0 koszt.

I odwrotnie, zakładamy, że G' ma wycieczkę h' kosztu najwyżej 0. Koszt krawędzi wE'0 i 1zgodnie z definicją. Dlatego każda krawędź musi mieć koszt0 jako koszt h' jest 0. Dlatego wyciągamy z tego wniosekh' zawiera tylko krawędzie w E.

W ten sposób udowodniliśmy to G ma cykl Hamiltona, wtedy i tylko wtedy, gdy G' kosztuje co najwyżej wycieczkę 0. TSP jest NP-kompletny.