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?
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?
Odpowiedzi:
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 i 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 P 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.
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:
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.