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

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?

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 $\mathsf{3SAT}$$\mathsf{3Color}$$\mathsf{3Partition}$ 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$\mathsf{HamiltonianCycle}$$\mathsf{HamiltonianPath}$$\mathsf{Clique}$$\mathsf{IndependentSet}$ 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.$\mathsf{PlanarCircuitSAT}$$\mathsf{PlanarTSP}$$\mathsf{3SAT}$$\mathsf{CircuitSAT}$

$\mathsf{Minesweeper}$$\mathsf{Tetris}$$\mathsf{OneCheckersMove}$$\mathsf{SuperMarioBros}$

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:

• $\mathsf{3SAT}$

• $\mathsf{3Color}$

• $\mathsf{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ą.

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.