Jakie są typowe techniki wzajemnego ograniczania problemów?


40

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.L1L2L2L1L1L2

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!


Zobacz tutaj kilka pomysłów na znalezienie odpowiednich partnerów i pomysły na obniżki.
Raphael

Odpowiedzi:


18

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.L1RL2RL1L2

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 RL2L1L2R

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

f(A,k)=(A,(1,,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 w(V,W,v,w)vVWw

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 φ kφkφk

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

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

f(A)={(A,12aAa),aAamod2=0(A,1+aA|a|),else

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)Akk

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 .Gs,tGkstGk

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)vG


2
Oto przykład zwany problemem podróżnego nabywcy (TPP), który ma wiele trudnych problemów w szczególnym przypadku.
Juho,

Innym przykładem obliczalności jest specjalny problem zatrzymania (który zwykle okazuje się nierozstrzygalny), szczególny przypadek ogólnego problemu zatrzymania.
Raphael

Czy KNAPSACK naprawdę jest poprawną redukcją z SUBSET-SUM? KNAPSACK pyta o wartość a SUBSET-SUM pyta o dokładną wartość, nie? Na przykład instancja SUBSET-SUM byłoby instancją „nie” (nie mogę uzyskać dokładnie 4 z tylko jednego elementu o wartości 5), ale redukcja KNAPSACK zmniejszyłaby to do i , więc byłoby to wystąpienie „tak” ... Czy coś mi brakuje? >=v{5},4{5},{1},4,15>4
Johnny

15

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

DOUBLE-SAT={φφ is a boolean formula with at least 2 satisfying assignments }

chcemy pokazać -kompletny. Szybko zauważamy, że jest bardzo blisko problemu, który już wiemy, że jest trudny, a mianowicie problemu satysfakcji (SAT) .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łę.NP

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ść .SATφv(v¬v)φv=⊥v=φφv

Wynika z tego, że jest -kompletny, co chcieliśmy pokazać.DOUBLE-SATNP

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.


6

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ładyL

MKfML

z problem zatrzymania (lub inny niezdecydowany język / problem).K={MM(M) 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:MfMfM

To samo działa, aby wykazać, że nie jest częściowo rozstrzygalny, wybierając języki nierozstrzygalne jako partner redukcji, np. :LK¯


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

-2

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).ABBA

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.


2
Zastanawiam się, czy zauważyłeś przypis w pytaniu. Myślę, że odpowiedzi powinny być bardziej szczegółowe i pokazywać, w jaki sposób stosowana jest określona metoda. Wydaje się to dość niejasne i ogólne. Jako ulepszenie, co powiesz o tym, jak można zbudować i używać gadżetów?
Juho

2
Ponadto: możesz wyjaśnić, dlaczego coś zależy od zaangażowanych klas złożoności i jak to zrobić. Co również, jeśli chcę przejść z do lub do , co mam wtedy zrobić? A co z „najbliższym problemem” - czy możesz podać przykład pary problemów? ABBA
Juho

PowerPoint pokazuje dwa przykłady używanych gadżetów. przykład najbliższego problemu: załóżmy, że mamy problem związany z teorią liczb. istnieje część G&J związana z teorią liczb. etcetera. podobnie jak w przypadku innych klas złożoności poza NP, jest ich wiele, ale listy problemów nie są tak dokładne ani łatwe do uzyskania. innymi słowy, aby zawęzić pierwotne pytanie, może powinno być ograniczone do całkowitych redukcji NP ...?
dniu

2
Zalecam dodanie do odpowiedzi wszystkich informacji, ponieważ komentarze mogą zostać usunięte w dowolnym momencie. Link do slajdów może również zostać zerwany jutro. O co mi chodziło z pobliskim problemem: co dokładnie robię , gdy znajdę problem, który wygląda podobnie (zakładam, że jestem początkującym)?
Juho,
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.