W teorii obliczalności i złożoności (i być może w innych dziedzinach) redukcje są wszechobecne. Istnieje wiele rodzajów, ale zasada pozostaje ta sama: pokaż, że jeden problem jest co najmniej tak samo trudny jak jakiś inny problem poprzez odwzorowanie instancji z na równoważne z rozwiązaniem w . Zasadniczo pokazujemy, że każdy solver dla może również rozwiązać jeśli pozwolimy mu używać funkcji redukcji jako preprocesora.$L_1$$L_2$$L_2$$L_1$$L_1$$L_2$

Przez lata dokonywałem swojej części redukcji i coś mnie wkurza. Chociaż każda nowa redukcja wymaga (mniej lub bardziej) kreatywnej konstrukcji, zadanie może wydawać się powtarzalne. Czy istnieje pula metod kanonicznych?

Jakie techniki, wzorce i sztuczki można regularnie stosować do konstruowania funkcji redukcji?

^{To ma stać się pytaniem referencyjnym . Dlatego prosimy o podanie ogólnych, dydaktycznie przedstawionych odpowiedzi, które są zilustrowane co najmniej jednym przykładem, ale mimo to obejmują wiele sytuacji. Dzięki!}

Przypadek specjalny

Zakładamy chcemy pokazać względem jakiegoś pojęcia redukcji . Jeśli jest szczególnym przypadkiem od , że jest dość banalna: w zasadzie możemy skorzystać z funkcji tożsamości. Intuicja stojąca za tym jest jasna: ogólny przypadek jest co najmniej tak samo trudny jak przypadek specjalny.$L_1 \leq_R L_2$$R$$L_1$$L_2$

W „praktyce”, daje nam i tkwią z problemem podnoszenia partnera redukcji dobry , czyli znalezienie szczególny przypadek , który okazał się być -hard.L 1 L 2$L_2$$L_1$$L_2$$R$

Prosty przykład

Załóżmy, że chcemy pokazać, że KNAPSACK jest trudny do NP. Na szczęście wiemy, że SUBSET-SUM jest NP-zupełny i rzeczywiście jest to szczególny przypadek KNAPSACK. Redukcja

$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$

wystarcza; to instancja KNAPSACK, która pyta, czy możemy osiągnąć co najmniej wartość z wartościami przedmiotów w tak aby odpowiednie wagi z pozostały poniżej w sumie. Nie potrzebujemy ograniczeń wagi do symulacji SUBSET-SUM, więc po prostu ustawiliśmy je na wartości tautologiczne.v V W $(V,W,v,w)$$v$$V$$W$$w$

Prosty problem z ćwiczeniami

Rozważ problem MAX-3SAT: biorąc pod uwagę formułę zdań i liczbę całkowitą , zdecyduj, czy istnieje interpretacja spełniająca co najmniej klauzule . Pokaż, że jest to trudne NP.k φ $\varphi$$k$$\varphi$$k$

3SAT to szczególny przypadek; przy wystarczy liczba klauzul w .m $f(\varphi) = (\varphi, m)$$m$$\varphi$

Przykład

Załóżmy, że badamy problem SUBSET-SUM i chcemy pokazać, że jest to trudny NP.

Mamy szczęście i wiemy, że problem PARTYCJI jest NP-zupełny. Potwierdzamy, że rzeczywiście jest to szczególny przypadek SUBSET-SUM i formułujemy

$\qquad \displaystyle f(A) = \begin{cases} \left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\ \left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else} \end{cases}$

gdzie jest zestawem wejściowym PARTITION, a jest instancją dla SUBSET-SUM, która pyta po podzbiorze sumującym do . Tutaj musimy zająć się sprawą, w której nie ma pasującego ; w takim przypadku dajemy arbitralną niewykonalną instancję.$A$$(A,k)$$A$$k$$k$

Problem z ćwiczeniami

Rozważmy problemu najdłuższej ścieżki: podany skierowany wykres węzły o i liczby całkowitej , decyduje, czy istnieje prosta droga od do w o długości co najmniej .$G$$s,t$$G$$k$$s$$t$$G$$k$

Pokaż, że NAJDŁUŻSZA ŚCIEŻKA jest NP-trudna.

CYKL HAMILTONA jest dobrze znanym problemem NP-zupełnym i szczególnym przypadkiem NAJDŁUŻSZEJ ŚCIEŻKI; do dowolnego węzła w wystarczająca. Zwróć uwagę w szczególności, że redukcja z HAMILTON-PATH wymaga więcej pracy.$f(G) = (G,v,v,n)$$v$$G$

Wykorzystanie znanego problemu w pobliżu

W obliczu problemu, który jest trudny, często dobrym pomysłem jest poszukiwanie podobnego problemu, który już okazał się trudny. Być może od razu zauważysz, że problem jest bardzo podobny do znanego problemu.

Przykładowy problem

Rozważ problem

chcemy pokazać -kompletny. Szybko zauważamy, że jest bardzo blisko problemu, który już wiemy, że jest trudny, a mianowicie problemu satysfakcji (SAT) .$\mathsf{NP}$

Przynależność do jest łatwa do pokazania. Certyfikat to dwa zadania. Oczywiście w czasie wielomianowym można sprawdzić, czy przypisania spełniają formułę.$\mathsf{NP}$

$\mathsf{NP}$ twardość wynika z redukcji z . Biorąc pod uwagę formułę , modyfikujemy ją, wprowadzając nową zmienną . Dodajemy do formuły nową klauzulę . Teraz, jeśli jest zadowalające, będzie zadowalające zarówno z i . Dlatego ma co najmniej 2 zadowalające zadania. Z drugiej strony, jeśli nie jest satysfakcjonujące, to na pewno nie będzie satysfakcjonujące bez względu na wartość .$\text{SAT}$$\varphi$$v$$(v \vee \neg v)$$\varphi$$v = \perp$$v = \top$$\varphi$$\varphi$$v$

Wynika z tego, że jest -kompletny, co chcieliśmy pokazać.$\text{DOUBLE-SAT}$$\mathsf{NP}$

Znajdowanie problemów w pobliżu

Zmniejszanie problemów jest rodzajem sztuki i często potrzebne jest doświadczenie i pomysłowość. Na szczęście wiele trudnych problemów jest już znanych . Komputery i nienaruszalność Gareya i Johnsona: Przewodnik po teorii kompletności NP jest klasyczny, a dodatek zawiera wiele problemów. Google Scholar jest także przyjacielem.

W obliczeniach często badamy zestawy maszyn Turinga. Oznacza to, że nasze obiekty są funkcjami i mamy dostęp do numeracji Gödla . To świetnie, ponieważ możemy robić, co chcemy, korzystając z funkcji wprowadzania danych, pod warunkiem, że pozostajemy obliczeniowi.

Załóżmy, że chcemy pokazać, że nie jest rozstrzygalne. Naszym celem jest osiągnięcie równoważności zagłady$L$

$\qquad \langle M \rangle \in K \iff \langle f_M \rangle \in L$

z problem zatrzymania (lub inny niezdecydowany język / problem).$K = \{ \langle M \rangle \mid M(\langle M \rangle) \text{ halts} \}$

Dlatego musimy wymyślić obliczalne¹ mapowanie , aby zawsze był obliczalny. Jest to akt twórczy oparty na równoważności zagłady. Zobacz kilka przykładów, aby dowiedzieć się, jak to działa:$\langle M \rangle \mapsto \langle f_M \rangle$$f_M$

• Ograniczenia mapowania do uzupełnienia$A_{\mathrm{TM}}$
• Czy możliwe jest mapowanie zredukować jeden z tych języków do drugiego?

To samo działa, aby wykazać, że nie jest częściowo rozstrzygalny, wybierając języki nierozstrzygalne jako partner redukcji, np. :$L$$\overline{K}$

• Czy prawidłowość języka jest akceptowana przez daną maszynę Turinga jako właściwość częściowo rozstrzygalna?
• Czy zbiór stałych obliczalnych funkcji jest rekurencyjnie wyliczalny?

1. Właśnie tutaj pojawia się numeracja Gödla: otrzymujemy możliwość obliczenia tego mapowania (zwykle) za darmo.

to zależy od złożoności klas zaangażowanych i czy ktoś chce zmniejszyć z danym do nieznanego lub nieznanym do danego . częstym scenariuszem jest udowodnienie problemów NP Hard lub NP Complete. powszechną techniką jest konstruowanie „gadżetów” w jednej domenie, które zachowują się w określony sposób, naśladując zachowanie innej domeny. na przykład, aby przekonwertować SAT na pokrycie wierzchołka, konstruuje się w gadżecie „gadżety”, które zachowują się podobnie do klauzul SAT, np. w następującym pokazie slajdów: NP Całkowite redukcje według Krishnamoorthy (również z przykładem ścieżki Hamiltona).$A$$B$$B$$A$

użyteczną strategią jest praca z dużymi kompilacjami problemów z danej klasy złożoności i znajdowanie „pozornie najbliższych problemów” do badanego problemu. doskonałym odniesieniem do tych linii jest Komputery i nienaruszalność, przewodnik po teorii kompletności NP, Garey i Johnson zorganizowane według różnych typów problemów.