Jak udowodnić, że problem jest kompletny?

108

Mam problem z planowaniem. Muszę udowodnić, że problem jest NP kompletny. Jakie mogą być metody, aby udowodnić, że NP jest kompletny?

algorithm thetna
źródło
Przeczytaj „Redukowalność wśród problemów kombinatorycznych” autorstwa Karpa.
Paul Hankin

Odpowiedzi:

146

Aby pokazać, że problem jest NP kompletny, musisz:

Pokaż, że jest w NP

Innymi słowy, mając pewne informacje C, możesz utworzyć algorytm czasu wielomianowego V, który zweryfikuje dla każdego możliwego wejścia, Xczy Xznajduje się w Twojej domenie, czy nie.

Przykład

Dowodzą, że problem pokryw wierzchołków (to jest w przypadku niektórych wykresie G, to ma zespół pokrywy wierzchołek wielkości ktak, że w każdej krawędzi Gposiada co najmniej jeden wierzchołek w zestawie pokrywy ?) W NP:

  • nasze dane wejściowe Xto jakiś wykres Gi pewna liczba k(to jest z definicji problemu)

  • Potraktuj nasze informacje Cjako „dowolny możliwy podzbiór wierzchołków na wykresie Go rozmiarze k”

  • Wtedy możemy napisać algorytm, Vktóry, biorąc pod uwagę G, ki Cpowróci, czy zbiór wierzchołków jest osłona na wierzchołek G, czy nie, w czasie wielomianowym .

Wtedy dla każdego wykresu G, jeśli istnieje jakiś „możliwy podzbiór wierzchołków w Grozmiarze k”, który jest pokryciem wierzchołka, to Gjest w NP.

Zauważ , że nie musimy szukać Cw czasie wielomianowym. Gdybyśmy mogli, problem byłby w `P.

Zauważ, że algorytm Vpowinien działać dla każdego G , dla niektórych C. Dla każdego wejścia powinny istnieć informacje, które pomogłyby nam zweryfikować, czy dane wejście znajduje się w domenie problemu, czy nie. Oznacza to, że nie powinno być danych wejściowych, jeśli informacje nie istnieją.

Udowodnij, że jest NP Hard

Obejmuje to uzyskanie znanego problemu NP-zupełnego, takiego jak SAT , zestawu wyrażeń boolowskich w postaci:

(A lub B lub C) i (D lub E lub F) i ...

gdzie wyrażenie jest spełnialne , to znaczy, że istnieje pewne ustawienie dla tych wartości logicznych, co sprawia, że ​​wyrażenie jest prawdziwe .

Następnie zredukuj problem NP-zupełny do swojego problemu w czasie wielomianowym .

Oznacza to, że mając pewne dane wejściowe Xdla SAT(lub dowolnego problemu NP-zupełnego, którego używasz), utwórz dane wejściowe Ydla swojego problemu, takie jak XSAT wtedy i tylko wtedy, gdy Yjest w twoim problemie. Funkcja f : X -> Ymusi działać w czasie wielomianowym .

W powyższym przykładzie danymi wejściowymi Ybyłby wykres Gi rozmiar otuliny wierzchołków k.

Aby uzyskać pełny dowód , musisz udowodnić oba:

  • to Xjest w SAT=> Yw twoim problemie

  • aw Ytwoim problemie => Xw SAT.

Odpowiedź marcoga ma związek z kilkoma innymi problemami NP-Complete, które możesz zredukować do swojego problemu.

Przypis: W kroku 2 ( Udowodnij, że jest NP-trudne ), zredukowanie innego problemu NP-trudnego (niekoniecznie NP-pełnego) do problemu bieżącego wystarczy, ponieważ problemy NP-zakończone są podzbiorem problemów NP-trudnych (które są także w NP).

Laila Agaev
źródło
7
Zastanawiam się, czy za tym stoi brak danych lub okrężne rozumowanie. Mam na myśli, jak „udowodnić”, że problem jest w NP, nie odnosząc go do innego problemu, który „już jest w NP”? To tak, jakby powiedzieć "jest zrobiony z żelaza, ponieważ wiadomo, że jego część jest żelazna", to nie jest żelazny dowód.
Hernán Eche,
6
O ile dobrze pamiętam, istnieje twierdzenie zwane twierdzeniem Cooka-Levina, które stwierdza, że ​​SAT jest NP-zupełny. Ten dowód jest nieco bardziej skomplikowany niż to, co opisałem powyżej i nie sądzę, żebym mógł go wyjaśnić własnymi słowami.
Laila Agaev,
4
Mówiąc dokładniej, twierdzenie Cooka-Levina stwierdza, że ​​SAT jest NP-zupełny: każdy problem w NP można zredukować w czasie wielomianowym za pomocą deterministycznej maszyny Turinga do problemu określenia, czy formuła Boole'a jest zadowalająca (SAT). Więc to jest brakujący element, o który pytałeś. Jeśli spojrzysz na twierdzenie w Wikipedii, znajdziesz dowód i możesz odwołać się do twierdzenia w swoim dowodzie. To powiedziawszy, redukcja SAT do danego problemu jest sposobem, w jaki nauczyłem się udowadniać NP-kompletność.
Laila Agaev,
Więc moje pytanie kończy się na tym, czy SAT można rozwiązać wielomianem, tj. Problem P = NP .. Dziękuję za odpowiedź.
Hernán Eche,
Czy mógłbyś wyjaśnić, dlaczego w drugim kroku nie możemy zredukować problemu NP-trudnego do problemu, którego chcemy? Czy musi to być problem NP-zupełny?
MLT
23

Musisz zredukować problem NP-Complete do problemu, który masz. Jeśli redukcji można dokonać w czasie wielomianowym, to udowodniłeś, że twój problem jest NP-zupełny, jeśli problem jest już w NP, ponieważ:

Nie jest to łatwiejsze niż problem NP-zupełny, ponieważ można go do niego sprowadzić w czasie wielomianowym, co czyni problem NP-trudnym.

Więcej informacji znajdziesz na końcu http://www.ics.uci.edu/~eppstein/161/960312.html .

moinudin
źródło
2
Daj +1 komuś, kto wyjaśnia to zrozumiale. zamiast mówić kilka odniesień do słów kluczowych, których prawie nie rozumiem.
ColacX
22
Pierwsze zdanie jest od początku do końca: musisz zredukować znany problem NP-zupełny do własnego problemu. To pokazuje, że twój problem jest co najmniej tak trudny, jak znany problem NP-zupełny. Część (b) jest również niepoprawna: jeśli znalazłeś redukcję, to już wiesz, że twój problem jest NP-trudny; jedyne pytanie brzmi, czy w ogóle jest w NP (niektóre problemy, takie jak Problem Haltingu, nie są). Jeśli jest NP-trudne, aw NP, to jest NP-zupełne (tj. „NP-zupełne” jest bardziej szczegółowe niż „NP-trudne”).
j_random_hacker
1
Nie powiedziałbym, że a) prowadzi do sprzeczności, ponieważ nie wiemy, że P! = NP.
Chiel ten Brinke
8

Aby udowodnić, że problem L jest NP-kompletny, musimy wykonać następujące kroki:

  1. Udowodnij, że twój problem L należy do NP (czyli biorąc pod uwagę rozwiązanie, możesz je zweryfikować w czasie wielomianowym)
  2. Wybierz znany problem NP-kompletny L '
  3. Opisz algorytm f, który przekształca L 'w L.
  4. Udowodnij, że twój algorytm jest poprawny (formalnie: x ∈ L 'wtedy i tylko wtedy, gdy f (x) ∈ L)
  5. Udowodnij, że algo f działa w czasie wielomianowym
Albert s
źródło
7

Po pierwsze, pokażesz, że w ogóle leży w NP.

Następnie znajdujesz inny problem, o którym już wiesz, że jest NP zakończony i pokazujesz, jak wielomianowo redukujesz problem NP Trudny do swojego problemu.

Lagerbaer
źródło
Nie. Musisz pokazać, że możesz zredukować od pełnego problemu NP do problemu NP, aby udowodnić kompletność NP ORAZ udowodnić, że w ogóle jest w NP. Trudno NP nie wchodzi w to, chyba że nie możesz tego udowodnić w NP.
mrmemio29
6
  1. Zapoznaj się z podzbiorem problemów NP Complete
  2. Udowodnij twardość NP: zredukuj dowolną instancję kompletnego problemu NP do instancji twojego problemu. To największy kawałek ciasta, a znajomość problemów NP Complete się opłaca. Redukcja będzie mniej lub bardziej trudna w zależności od wybranego problemu NP Complete.
  3. Udowodnij, że twój problem jest w NP: zaprojektuj algorytm, który będzie w stanie zweryfikować w czasie wielomianowym, czy instancja jest rozwiązaniem.
UmNyobe
źródło