POŁOWA KLIQUE - NP Kompletny problem

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 $\langle G \rangle$$G$$n/2$$G$

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.$k$$k$
• Według naszego podręcznika, „ Wprowadzenie do teorii obliczeń ” Michaela Sipsera , str. 268, że problem CLIQUE = { | jest nieukierowanym wykresem z klika} w NPG $\langle G,k\rangle$$G$$k$
• 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.$\text{size} \geq n/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!

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 /$G=(V, E)$$H=(V', E')$$G$$k$$H$$n/2$

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.$\ge$

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 $G$$k$$H$$H$$G$$k$

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.$H$$G$

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.