Redukcje z książki.

Jest to zgodne z „ Algorytmami z książki ”. Chociaż redukcje są również algorytmami, pomyślałem, że wątpliwe jest, aby pomyśleć o redukcji w odpowiedzi na pytanie o algorytmy z książki. Stąd osobne zapytanie!

Wszelkie redukcje są mile widziane.

Zacznę od bardzo prostej redukcji od osłony wierzchołków do multikutów na gwiazdach. Redukcja prawie sugeruje się sama po zidentyfikowaniu problemu źródłowego (przed którym trudno mi było uwierzyć, że problem byłby trudny dla gwiazd). Ta redukcja polega na skonstruowaniu gwiazdy o liściach i skojarzeniu pary końcówek z każdą krawędzią na wykresie, i „łatwo zauważyć”, że to działa. Zaktualizuję to, dodając link do referencji, gdy tylko ją znajdę.$n$

Ci, którym brakuje kontekstu książki, mogą spojrzeć na pytanie o Algorytmy z książki .

Aktualizacja: Zdaję sobie sprawę, że nie do końca wiedziałem, co kwalifikuje się jako redukcja z książki. Wydaje mi się, że ten problem jest nieco trudny, więc przyznam się do celowego uchylania się od niego przez wślizgnięcie się w odniesienie do innego wątku :)

Opiszę więc, co miałem na myśli i przypuszczam, że jest to oczywiste - w tym względzie YMMV. Zamierzam bezpośrednią analogię do pierwotnego zamiaru Dowodów z Księgi. Widziałem redukcje, które są okropnie sprytne i zostawiam rozdziawione, jak ta sekwencja myśli mogła przydarzyć się każdemu. Podczas gdy takie redukcje pozostawiają mnie z wyraźnym podziwem, nie są to przykłady, które chcę zebrać w tym kontekście.

To, czego szukam, to redukcje, które są opisane bez większych trudności i być może są nieco zaskakujące, ponieważ są łatwe do uchwycenia, ale nie są łatwe do wymyślenia. Jeśli oszacujesz, że przedmiotowa redukcja będzie wymagała wykładu, to prawdopodobnie nie będzie pasować do rachunku, chociaż jestem pewien, że mogą istnieć wyjątki, w których pomysł na wysokim poziomie jest elegancki, a diabeł tkwi w szczegółach (na przykład nagranie, nie jestem pewien, czy mogę coś wymyślić).

Podany przeze mnie przykład był celowo prosty i, mam nadzieję, nieco - jeśli nie idealnie - ilustrujący te cechy. Pierwszy raz, gdy usłyszałem o cięciu wielokrotnym, był w klasie, a nasz instruktor zaczął od stwierdzenia, że ​​nie tylko jest to NP-trudne w ogóle, ale jest NP-trudne nawet, gdy ogranicza się do drzew ... {dramatyczna pauza} wysokości jeden . Pamiętam, że nie byłem w stanie tego udowodnić od razu, chociaż z perspektywy czasu wydaje się to oczywiste.

Przypuszczam , że oczywiste z perspektywy czasu dokładnie opisuje to, czego szukam. Nie jestem pewien, czy ma to coś wspólnego ze złożonością opisu - być może zdarzają się sytuacje, w których coś pozornie mrocznego może zostać zaklasyfikowane jako eleganckie - zachęcamy do przedstawienia swoich przykładów (wyjątków?), Ale naprawdę doceniłbym uzasadnienie. Biorąc pod uwagę, że po pewnym czasie jest to kwestia gustu, na pewno powinieneś swobodnie znaleźć to, co uważam za niezwykle złożone, idealnie piękne. Nie mogę się doczekać, aby zobaczyć wiele przykładów!

Rabin pokazuje jednokierunkowość (x ^ 2 mod N = pq) bez faktoryzacji N przez redukcję pokazującą, że jeśli możesz wziąć moduł pierwiastków kwadratowych N = pq, możesz czynnik N.

W uczeniu maszynowym istnieje wiele interesujących redukcji. Oto kilka przykładów:

• klasyfikacja wieloklasowa na klasyfikację binarną ( link ) - można rozwiązać problem wyboru spośród wielu klas, rozwiązując łatwiejsze problemy wyboru między dwoma.
• mocne uczenie się do słabego uczenia się ( przyspieszanie ) - można osiągnąć arbitralnie niski poziom błędów, biorąc pod uwagę możliwość osiągnięcia nieco lepszej niż losowej.
• ranking do klasyfikacji ( link )
• kwadratowa strata do klasyfikacji ( sondowanie ) - można oszacować prawdopodobieństwo przynależności do klasy za pomocą klasyfikatora o niskim poziomie błędu.

Poradnik Aliny Beygelzimer, John Langford i Bianca Zadrożny obejmuje kilka innych.

Twierdzenie Cooka-Levina

Każdy problem w NP można zredukować w czasie policyjnym przez deterministyczną maszynę Turinga do SAT. Odnośnik patrz 1 .

Mnożenie liczb całkowitych do szybkich transformacji Fouriera!

Twierdzenie Rice'a

Jeden z moich ulubionych. Zmniejsza problem zatrzymania do dowolnego zestawu indeksów (lub jego uzupełnienia). Patrz na przykład Sipser, problem 5.28.

SAT do 3SAT

$k$$k \gt 3$

3SAT do 3COL

Korzystanie z gadżetów w celu zredukowania 3SAT do problemu decydowania o tym, czy wykres można pokolorować za pomocą 3 kolorów. W celach informacyjnych patrz 1 .

W sensie mówiąc - och, to było proste - z perspektywy czasu:

redukując sortowanie do problemu wypukłego kadłuba.

DOKŁADNE POKRYCIE ZA POMOCĄ 3-ZESTAWÓW DO PODSETOWANIA SUMY

$U=\{1,2,\ldots,3m\}$$S_1,\ldots,S_n$$U$$m$$U$

$w_1,\ldots,w_n$$K$$K$

$S_i$$\{0,1\}^{3m}$$n+1$$S_i$$w_i=\sum_{j\in S_i} (n+1)^{3m-j}$$K=\sum_{j=0}^{3m-1} (n+1)^j$

(Moim źródłem była książka Papadimitriou.)