Twardość i kierunki redukcji

Powiedzmy, że wiemy, że problem A jest trudny, a następnie redukujemy A do nieznanego problemu B, aby udowodnić, że B jest również trudny.

Jako przykład: wiemy, że 3-kolorowanie jest trudne. Następnie redukujemy kolorowanie 3 do koloru 4. Po połączeniu jednego z kolorów 3-kolorowania masz 4-kolory, ergo 4-kolory są trudne.

Właśnie tak. Ale dlaczego jest to dowód na to, że 4-kolorowanie jest trudne? Czy możesz użyć rozwiązania problemu kolorowania 4, aby rozwiązać problem kolorowania 3? Jeśli tak to jak? Jeśli nie, dlaczego jest to ważny dowód?

Premia q: Czy redukcje wielomianowe muszą być możliwe w obie strony?

Edycja: jeśli możesz wyjaśnić, dlaczego tak jest, na przykład zrobiłbyś w Internecie przysługę. Nigdzie nie mogłem tego wyjaśnić w konkretny sposób.

complexity-theory np-complete reductions

— The Unfun Cat
źródło

Jeśli masz do czynienia z dwoma problemami NP-zupełnymi, to tak, muszą wystąpić redukcje wielomianowe, które przebiegają w obie strony. W wielu przypadkach redukcje z A do B i z B do A mogą wyglądać bardzo różnie.

— Joe

Jeśli oba problemy nie należą do tej samej klasy złożoności, może nie nastąpić redukcja w obie strony.

— Joe

Zmniejszenie z problemów do innego problemu, jest transformacja o każdym przypadku, od do wystąpienia od , w taki sposób, $A$ $B$ $f$ $a$ $A$ $f(a)$ $B$

x \in A \Leftrightarrow f (x) \in B (E)

$\qquad\qquad x∈A ~~⇔~~ f(x)∈B \qquad \qquad (E)$

Jeśli jest transformacją zachowującą złożoność, którą jesteś zainteresowany (np. jest transformacją wielomianową, jeśli weźmiesz pod uwagę twardość), to istnienie algorytmu rozwiązująca implikuje istnienie algorytmu rozwiązującego : wystarczy uruchomić , a następnie . $f$ $f$ $\mathsf{NP}$ $\mathcal A_B$ $B$ $A$ $f$ $\mathcal A_B$

Stąd istnienie takiej redukcji z do oznacza, że nie jest łatwiejsze niż . Zmniejszenie nie jest konieczne w drugą stronę. $A$ $B$ $B$ $A$

Na przykład do kolorowania wykresów. Możesz zredukować 3-kolorowanie do 4-kolorowanie, ale nie w bezpośredni sposób. Jeśli weźmiesz wykres i wybierzesz , będziesz mieć ale nie masz oczywiście. Wniosek jest taki, że równoważność nie jest spełniony, to jest nie ograniczenie. $G$ $f(G)=G$ $x∈3\mathsf{COL}$ $⇒$ $f(x)∈4\mathsf{COL}$ $f(x)∈4\mathsf{COL}$ $⇒$ $x∈3\mathsf{COL}$ $(E)$ $f$

Możesz zbudować poprawną redukcję z do ale jest to trochę bardziej skomplikowane: dla dowolnego wykresu , niech będzie wykresem rozszerzonym o inny węzeł który jest połączony z krawędzią do każdego innego węzła. $f$ $3\mathsf{COL}$ $4\mathsf{COL}$ $G$ $f(G)$ $G$ $u$

Transformacja zachowuje złożoność (tutaj wielomian);
jeśli ma to ma : po prostu użyj czwartego koloru dla ; $G$ $3\mathsf{COL}$ $f(G)$ $4\mathsf{COL}$ $u$
jeśli ma wartość , możesz udowodnić, że wszystkie węzły oprócz mają kolor, który nie jest ciebie , stąd ma wartość . $f(G)$ $4\mathsf{COL}$ $u$ $u$ $G$ $3\mathsf{COL}$

Dowodzi to, że jest redukcją i że jest trudniejszy niż . Możesz udowodnić w ten sam sposób, że jest trudniejszy niż dla dowolnego , co jest interesującym dowodem na to, że jest trudniejszy niż jakikolwiek . $f$ $4\mathsf{COL}$ $3\mathsf{COL}$ $n\mathsf{COL}$ $m\mathsf{COL}$ $n≥m$ $3\mathsf{COL}$ $n\mathsf{COL}$

— jmad
źródło

Dlaczego taka redukcja oznacza, że B nie jest łatwiejsze niż A? UV dla wysiłku, ale zbyt abstrakcyjne dla mojego mizernego mózgu.

— The Unfun Cat

Czy to znaczy, że odpowiedź będzie taka sama dla B jak dla A po zmniejszeniu A do B? Myślę, że rozumiem: jeśli pierwotne wystąpienie ma trzy kolory, to przekształcone wystąpienie będzie miało cztery kolory, więc jeśli odpowiedź brzmi „tak, ma cztery kolory”, odpowiedź brzmi również „tak, ma trzy kolorowanki "? Ale czy nadal nie jest możliwe, że transformowana instancja B ma cztery kolory, a A nie ma trzech kolorów? Wyobrażam sobie, że łatwiej jest pokolorować wykres czterema kolorami ...

— The Unfun Cat

@TheUnfunCat (zaktualizowany o przykład kolorowania 3 i 4)

— jmad