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ę.
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!