POŁOWA KLIQUE - NP Kompletny problem

20

Zacznę od zauważenia, że jest to problem związany z pracą domową, proszę podać tylko porady i związane z nimi obserwacje, proszę BEZ BEZPOŚREDNIEJ ODPOWIEDZI . Powiedziawszy to, oto problem, na który patrzę:

Niech HALF-CLIQUE = { | jest nieukierowanym wykresem posiadającym pełny podsgraf z co najmniej węzłami, gdzie n jest liczbą węzłów w }. Pokaż, że PÓŁKLIKAT jest NP-kompletny.G n / 2 GGGn/2G

Poza tym wiem, co następuje:

  • Pod względem tego problemu klika jest definiowana jako nieukierowany podgraf wykresu wejściowego, w którym każde dwa węzły są połączone krawędzią. -clique jest klika, który zawiera węzłów.kk
  • Według naszego podręcznika, „ Wprowadzenie do teorii obliczeń ” Michaela Sipsera , str. 268, że problem CLIQUE = { | jest nieukierowanym wykresem z klika} w NPG kG,kGk
  • Ponadto, według tego samego źródła (na str. 283) zauważa, że ​​CLIQUE jest w NP-Complpete (a więc oczywiście również w NP).

Wydaje mi się, że mam tutaj jądro odpowiedzi, ale mógłbym użyć jakiegoś wskazania, co jest z nim nie tak lub jakichkolwiek powiązanych punktów, które mogą być istotne dla odpowiedzi . To ogólny pomysł, jaki do tej pory mam,

Ok, najpierw zauważę, że certyfikat byłby POŁÓWKĄ QLIQUE z . Teraz wydaje się, że musiałbym stworzyć weryfikator, który jest wielomianową redukcją czasu z CLIQUE (który, jak wiemy, to NP-Complete) na PÓŁKLIKNIĘCIE. Moim pomysłem byłoby, aby to zrobić poprzez stworzenie maszyny Turinga, która uruchamia weryfikator maszyny Turinga w książce dla CLIQUE z dodatkowym ograniczeniem dla PÓŁKLIWY.sizen/2

Brzmi to dla mnie poprawnie, ale tak naprawdę nie ufam sobie w tym temacie. Jeszcze raz chciałbym przypomnieć wszystkim, że jest to PROBLEM Z DOMEM, więc staraj się unikać odpowiedzi na pytanie. Wszelkie wskazówki, które tego nie spełnią, będą mile widziane!

BrotherJack
źródło

Odpowiedzi:

15

Sądząc po twoim opisie i komentarzach, najlepiej pomoże ci dokładny opis, w jaki sposób można zastosować redukcje w celu udowodnienia kompletności NP:

Problem polega na tym, że NP jest kompletny, jeśli jest w NP i jest trudny do NP. Oznacza to, że każdy dowód kompletności NP składa się z dwóch części: dowodu, że problem leży w NP i dowodu, że jest to NP-trudny.

W pierwszej części musisz wykazać, że wystąpienia YES można zweryfikować w czasie wielomianowym przy użyciu odpowiedniego certyfikatu. Alternatywnie możesz pokazać, że problem można rozwiązać w czasie wielomianowym za pomocą niedeterministycznej maszyny Turinga, ale zwykle nie dzieje się tak, ponieważ łatwo można popełnić błędy.

W twoim przypadku sprowadza się to do udowodnienia, że ​​dla każdego wykresu z kliką możesz znaleźć jakiś dowód, że rzeczywiście istnieje taka klika, że ​​uzbrojeni w taki dowód możesz sprawdzić w czasie wielomianowym, że rzeczywiście istnieje taka klika.n/2

W drugiej części musisz wykazać, że problem jest trudny NP. Jest to prawie we wszystkich przypadkach wykazane przez udowodnienie, że twój problem jest co najmniej tak trudny, jak jakiś inny trudny problem NP. Jeśli PÓŁKLIKAT jest co najmniej tak samo twardy jak KLIKA, musi być również NP-trudny.

Robisz to, udowadniając redukcję Z KLIKNIĘCIA DO PÓŁKLIWY. „Ograniczasz” problem, czyniąc go „łatwiejszym”. Mówisz: „Rozwiązanie CLIQUE jest trudne, ale udowodniłem, że wystarczy rozwiązać PÓŁKLIKAT, aby rozwiązać CLIQUE”. (wiele osób, nawet ekspertów, czasami mówi to w niewłaściwy sposób :))

Istnieją różne rodzaje redukcji: najczęściej stosowaną redukcją jest ta, w której odwzorowujesz instancje w tym przypadku CLIQUE na instancje PÓŁKLIWKI, których rozmiar jest co najwyżej wielomianowo większy, w czasie wielomianowym. Oznacza to, że jeśli uda nam się rozwiązać POŁOWĘ CLIQUE, to możemy również rozwiązać CLIQUE, łącząc algorytm i redukcję.

Innymi słowy, musimy pokazać, że możemy rozwiązać CLIQUE, jeśli możemy rozwiązać PÓŁKLIKAT. Robimy to, pokazując, że dla każdej instancji dla CLIQUE możemy zaprojektować instancję HALF-CLIQUE, tak aby instancja CLIQUE była instancją „tak”, a instancja HALF-CLIQUE jest instancją „tak”.

Dowód zaczyna się zatem w ten sposób: biorąc pod uwagę wykres , mogę utworzyć wykres tak, aby zawierał klik iff zawiera klique. Zostawię tę część tobie (ta część wymaga kreatywności, część dotycząca konkretnego problemu).H = ( V , E ) G k H n / 2G=(V,E)H=(V,E)GkHn/2

Alex ten Brink
źródło
Doskonała konfiguracja, myślę, że wykonałeś bardzo dobrą robotę, dostarczając wystarczającą ilość informacji, aby poprowadzić Cię bez udzielania odpowiedzi i robienia tego w elokwentny sposób. Dziękuję Ci.
BrotherJack,
1
Coś takiego należy umieścić w wiki tagu np-complete na przyszłość. Czy mógłbyś?
Raphael
8

Wydajesz się trochę zagubiony. Chcesz pokazać, że PÓŁ-CLIQUE CLIQUE, co oznacza, że ​​szukasz algorytmu wieloczasowego, który przyjmuje instancje CLIQUE jako dane wejściowe i wyjściowe instancji PÓŁ-CLIQUE z właściwością, że „tak” dane wejściowe są mapowane na „tak” es i „no” wejścia odwzorowują na „no” s.

Zasadniczo więc zadaniem jest pobranie wykresu i liczby i wygenerowanie nowego wykresu (i bez liczby), aby miał klikę na co najmniej połowie jej wierzchołków, ilekroć ma klikę o rozmiarze . k H H G kGkHHGk

Poniższy spoiler zawiera wskazówkę, jak wykonać tę redukcję:

Spróbuj zrobić , przyczepiając (w pewien sposób) odpowiednio dobraną klikę do , plus pewną liczbę wierzchołków niepowiązanych z niczym.G.HG

Louis
źródło
Nie rozumiem co mówisz. To, co próbowałem zrobić, to zredukować PÓŁKLIKAT do CLIQUE, modyfikując wariator użyty w książce, aby udowodnić, że CLIQUE to NP, niech uruchomi się na wykresie wejściowym G, a jeśli znajdzie CLIQUE, sprawdzi, czy wspomniany CLIQUE zawiera co najmniej n / 2 węzłów, gdzie n jest liczbą węzłów w G. Czy taki weryfikator PÓŁKLIWY nie pokazałby, że weryfikator KSIĘGI jest jego zredukowaną postacią (jak w podrzędnym problemie rozwiązania PÓŁKLIKACJI )?
BrotherJack,
A może mówisz, że mam to odwrotnie i muszę udowodnić, że CLIQUE musi zostać zredukowany do PÓŁKLIKACJI? Zupełnie też nie dostaję twojego spoilera. Czy jest jakiś sposób, aby to wyjaśnić bez podania odpowiedzi?
BrotherJack,
3
Tak, aby pokazać problem jest NP-zupełny, musisz (a) pokazać, że jest w NP oraz (b) zmniejszyć niektóre znane NP-trudny problem do niego. Aby zapamiętać właściwy kierunek redukcji, chodzi o wykorzystanie nowego problemu jako „czarnej skrzynki” dla skutecznego rozwiązania znanego problemu NP-C.
Louis,
OK, myślę, że teraz rozumiem. Dzięki za pomoc!
BrotherJack,
+1 Chyba mam to. Twoja wskazówka była bardzo pouczająca, kiedy zrozumiałem, co robię źle. Dzięki jeszcze raz!
BrotherJack,
0

Możesz zmniejszyć problem z pokrywą wierzchołków. Jeśli wykres dopełnienia danego wykresu ma pokrycie wierzchołków mniejsze niż n / 2 węzłów, wówczas wykres ten będzie miał klikę większą niż n / 2 węzłów, czyli będzie półklikiem. Po prostu powiedz, że trudno jest rozwiązać problem z Wierzchołkiem Wierzchołków, tak też jest.

Arnav
źródło
1
Ponieważ można zmniejszyć od jakiegokolwiek problemu NP-zupełny, to nie jest strasznie użyteczne. Szczegóły dotyczące redukcji są oczekiwane.
Raphael
Jest to tylko redukcja w stosunku do specjalnego przypadku znalezienia pokrycia wierzchołków o wielkości co najwyżej , a nie ogólnego problemu pokrycia wierzchołków. Chociaż ten szczególny przypadek jest nadal trudny do przeprowadzenia w NP, wciąż musisz to udowodnić, najprawdopodobniej poprzez redukcję ogólnego problemu pokrycia wierzchołków. To jest prawie to samo pytanie, co oryginalne, tylko teraz dla osłony wierzchołków zamiast kliki, ale metoda jest bardzo podobna. n/2
Dyskretna jaszczurka