Jak skonstruować redukcje między problemami, aby udowodnić, że problem jest NP-kompletny?


27

Biorę kurs złożoności i mam problem z wymyśleniem redukcji między problemami NPC. Jak znaleźć redukcje między problemami? Czy istnieje ogólna sztuczka, której mogę użyć? Jak podejść do problemu, który wymaga ode mnie udowodnienia, że ​​jest nim NPC?


4
Przepraszam za rozczarowanie, nie sądzę, że istnieje metoda, która rozwiązuje wszystko. Podobnie jak wiele problemów w życiu, każdy jest wyjątkowy. Mam nadzieję, że z czasem dostaniesz odpowiednie przeczucie, jak je rozwiązać.
Ran G.

1
Czy istnieją jakieś przydatne wskazówki, jak podejść do takich problemów? Jestem całkowicie zagubiony, gdy widzę pytanie, które wymaga ode mnie udowodnienia, że ​​to NPC. Jak mam do nich podejść?
Anonimowy

Odpowiedzi:


45

Nie ma magicznej kuli; Dowody twardości NP są trudne. Istnieją jednak ogólne ramy dla wszystkich takich dowodów. Wielu uczniów, którzy zmagają się z dowodami twardości NP, jest zdezorientowanych co do tego , co powinni robić, co oczywiście uniemożliwia ustalenie, jak to zrobić. Oto co należy zrobić, aby udowodnić problem NP-trudny.

Po pierwsze, chyba że po prostu odrabiasz pracę domową, musisz zdecydować, który trudny problem NP należy zredukować do swojego problemu . Jest to w dużej mierze kwestia „zapachu”. Jeśli liczba 3 pojawia się w dowolnym miejscu w opisie problemu, spróbuj zmniejszyć z lub 3 C o l o r lub 3 P a r t i t i o n . (Tak, ja poważny). Jeżeli problem polega na znalezieniu optymalnych lub podciąg permutacji lub ścieżkę należy zmniejszyć z H a m ı l t o n i3SAT3Color3Partition lub H a m i l t o n i a n P a t h . Jeśli twój problem wymaga najmniejszego podzbioru o określonej właściwości, spróbuj C l i q u e ; jeśli prosi o największy podzbiór o określonej właściwości, spróbuj I n d e p e n d e n t S e t . Jeśli twój problem polega na zrobieniu czegoś w samolocie, spróbuj PHamiltonianCycleHamiltonianPathCliqueIndependentSet lub P l n R T S P . I tak dalej. Jeżeli problem nie „zapach” jak niczego, 3 S T lub C ı r c u ı t S T prawdopodobnie jest najlepszy.PlanarCircuitSATPlanarTSP3SATCircuitSAT

MinesweeperTetrisOneCheckersMoveSuperMarioBros

Po drugie, faktyczna redukcja. Aby zredukować problem X (ten, o którym wiesz, że jest NP-trudny) do problemu Y (ten, który próbujesz udowodnić, że jest NP-trudny, musisz opisać algorytm, który przekształca dowolną instancję X w legalną instancję Y Algorytm redukcji musi zrobić coś konkretnego z każdą „funkcją” instancji X, część wyniku dla każdej „funkcji” jest zwykle nazywana gadżetem .

Ale czym jest funkcja? To zależy od problemu X. Na przykład:

  • 3SAT

  • 3Color

  • PlanarCircuitSat

Rzeczywista forma gadżetu zależy od problemu Y, którego właśnie redukującego do . Na przykład, jeśli sprowadzasz się do problemu związanego z grafami, gadżetami będą małe podgrupy; zobacz artykuł w Wikipedii. Jeśli ograniczasz się do planowania, każdy gadżet będzie zestawem zadań do zaplanowania. Jeśli sprowadzasz się do problemu związanego z Mario , każdy gadżet będzie zestawem klocków, klocków i Koopas.

Może to być mylące, jeśli oba problemy dotyczą tego samego rodzaju obiektu. Na przykład, jeśli zarówno X, jak i Y mają problemy z grafami, twój algorytm przekształci jeden wykres (instancja X) w inny graf (instancja Y). Wybierz swój zapis mądrze, aby nie pomylić tych dwóch wykresów. Zdecydowanie zalecam także stosowanie wielu kolorów atramentu.

Wreszcie algorytm redukcji musi spełniać trzy właściwości:

  • Działa w czasie wielomianowym. (Zazwyczaj jest to łatwe.)

  • Jeśli twój algorytm redukcji otrzyma dodatnią instancję X jako dane wejściowe, produkuje dodatnią instancję Y jako dane wyjściowe.

  • Jeśli twój algorytm redukcji wytwarza dodatnią instancję Y jako danych wyjściowych, musi zostać podana dodatnia instancja X jako danych wejściowych.

Jest tu ważna subtelność. Twój algorytm redukcji działa tylko w jednym kierunku, od instancji X do instancji Y, ale udowodnienie poprawności algorytmu wymaga uzasadnienia transformacji w obu kierunkach. Musisz także pamiętać, że twój algorytm redukcji nie jest w stanie stwierdzić, czy dana instancja X jest dodatnia czy ujemna - wymagałoby to rozwiązania problemu trudnego dla NP w czasie wielomianowym!

Właśnie to . Jak tylko przychodzi z praktyką.


5
3SAT3SATptruefalse

1
Odnośnie do „Jeśli algorytm redukcji wytwarza dodatnią instancję Y jako danych wyjściowych, należy podać pozytywną instancję X jako danych wejściowych”: Chociaż bardziej intuicyjnym wydaje się zapisanie tego warunku jako „Jeśli algorytm redukcji ma instancję ujemną X jako dane wejściowe, tworzy ujemną instancję Y jako dane wyjściowe ”, zauważ, że te dwa warunki są równoważne , a sposób, w jaki napisał to JeffE, zwykle znacznie ułatwia konstruowanie dowodu , ponieważ w każdym przypadku„ coś masz ”(albo pozytywne wystąpienie X lub pozytywne wystąpienie Y) do pracy.
j_random_hacker

11

JeffE przedstawia najczęstszą strategię: poznaj wiele problemów z kompletowaniem NP, znajdź taki, który bardzo dobrze pasuje i dokonaj łatwej redukcji.

Inną prawidłową strategią jest zawsze używanie 3SAT (lub innego problemu). Może to uczynić pewne redukcje bardziej skomplikowany, ale Plusem jest to, że masz dużo doświadczenia wyrażającego satifiability w innych typach problemów. Dzięki temu oszczędzasz czas na znalezienie dobrego partnera redukcyjnego (w tym ślepych zaułków) i masz nadzieję, że twoje doświadczenie pozwoli ci dokonać redukcji szybko, nawet jeśli jest to trudniejsze.

Podejście to ma również pewne meta piękno: (3) SAT jest jednym z niewielu problemów, dla których kompletność NP została udowodniona (prawie) bezpośrednio. Dlatego poleganie tylko na tym dowodzie utrzymuje twoje „drzewo dowodu” płasko, unikając długich łańcuchów redukcji.


3
Bezpośrednie udowodnienie, że problem związany z zatrzymaniem jest kompletny NP, gdy granica jest podana jednostronnie, nie jest zbyt trudne i jest łatwym sposobem udowodnienia, że istnieje jakiś problem NP-zupełny, nawet jeśli sam problem jest raczej bezużyteczny do zmniejszenia.
Alex ten Brink

3
Nie jestem pewien co do twierdzenia, że ​​jest to jedyny problem, który okazał się być NP-zupełny bezpośrednio. W rzeczywistości, jeśli interpretujesz to w ścisłym tego słowa znaczeniu, jest to zdecydowanie nieprawda. Artykuł Cooka z 1971 r. Mówi o TAUT, a nie SAT (wykorzystuje redukcje Cooka, a nie redukcje Karp) (łatwo jest spostrzec, że dowód również dowodzi, że SAT jest NP-zupełny pod redukcjami Karp).
Kaveh

@Kaveh Huh? Tautologia jest kompletna co-Np i dlatego nie jest znana z NP (-kompletna). Nie przeczytałem jednak artykułu Cooka.
Albert Hendriks,

1
@Albert, więc powinieneś to przeczytać. Dzięki obniżkom wartości Cooka nie można rozróżnić NP i coNP.
Kaveh
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.