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.

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$

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}$