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 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.
- Według naszego podręcznika, „ Wprowadzenie do teorii obliczeń ” Michaela Sipsera , str. 268, że problem CLIQUE = { | jest nieukierowanym wykresem z klika} w NPG 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.
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!
źródło
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 kG k H H G k
Poniższy spoiler zawiera wskazówkę, jak wykonać tę redukcję:
źródło
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.
źródło