Złożoność obliczeniowa/Wykałd 4: Redukcje i zupełność

Redukcje i zupełność

W poprzednim module przedstawione zostały podstawowe klasy złożoności dla problemów, jak również zależności między nimi. W tym rozdziale poznamy narzędzie bardzo pomocne przy określaniu przynależności problemów do zadanej klasy złożoności - redukcje.

Redukcje

Definicja

Niech ${ℱ}$ będzie pewną rodziną funkcji o sygnaturze

 $\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$

domkniętą na składanie i zawierającą identyczność. Niech $L_1$ i $L_2$ będą językami nad alfabetem $\{0,1\}$ (czyli inaczej mówiąc zakodowanymi binarnie problemami decyzyjnymi). Mówimy, że problem $L_1$ jest redukowalny do problemu $L_2$ w sensie rodziny ${ℱ}$ i zapisujemy

 $L_1{\le }_{{ℱ}}{L}_2$

wtedy i tylko wtedy, gdy

 ${\mathrm{\exists }}_{f\in {ℱ}}{\mathrm{\forall }}_{w\in \{0,1{\}}^{\star }}w\in L_1⟺f(w)\in L_2$

Intuicyjnie problem $L_1$ jest w pewnym sensie co najwyżej tak trudny jak problem $L_2$ - jeżeli znamy rozwiązanie problemu $L_2$ oraz odpowiednią funkcję (zwaną redukcją lub transformacją), to znamy również rozwiązanie problemu $L_1$. Warto zauważyć, że relacja ${\le }_{{ℱ}}$ jest preporządkiem, to znaczy jest zwrotna (ze względu na obecność identyczności) i przechodnia (ze względu na domkniętość rodziny ${ℱ}$ na składanie).

Przedstawmy teraz najczęściej stosowane rodziny redukcji.

Redukcje wielomianowe

Rodzina redukcji wielomianowych (Karpa) to rodzina funkcji $\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$ obliczalnych nadeterministycznej maszynie Turinga w czasie wielomianowym. Redukowalność w sensie rodziny redukcji wielomianowych najczęściej po prostu nazywa się redukowalnością wielomianową.

Klasycznym przykładem redukowalnosci wielomianowej jest redukowalność problemu maksymalnego skojarzenia w grafie dwudzielnym do problemu maksymalnego przepływu w grafie skierowanym.

ZO-4-1. Przekształcenie grafu dwudzielnego w sieć przepływową.

Redukcje wielomianowe mają ważną własność: Jeżeli problem $L_1$ jest redukowalny wielomianowo do problemu $L_2$ oraz $L_2$ należy do klasy $P$, to $L_1$ również należy do klasy $P$. Aby uzasadnić tą własność wystarczy skonstruować maszynę, która najpierw przekształci instancję problemu $L_1$ do instancji problemu $L_2$ (uczyni to w czasie wielomianowym, bo $L_1$ jest wielomianowo redukowalne do $L_2$), po czym w czasie wielomianowym da odpowiedź dla instancji problemu $L_2$.

Ćwiczenie 1

Załóżmy, że $L_1$ jest wielomianowo redukowalne do $L_2$ oraz $L_2$ należy do klasy $NP$. Pokaż, że $L_1$ również należy do klasy $NP$.

Rozwiązanie

Należy tutaj skorzystać z faktu, że deterministyczna maszyna Turinga jest specjalnym przypadkiem maszyny niedeterministycznej. Wystarczy zatem najpierw uruchomić deterministyczną maszynę implementującą redukcję z $L_1$ do $L_2$, po czym uruchomić niedeterministyczną maszynę, rozwiązującą problem $L_2$ w czasie wielomianowym. Otrzymamy w tym momencie niedeterministyczną maszynę rozwiązującą problem $L_1$. Należy jeszcze tylko uzasadnić, czemu łączny czas działania tej maszyny będzie wielomianowo zależny od wielkości wejścia; wiemy jednak, że wyjście redukcji jest co najwyżej wielomianowo zależne

od wielkości wejścia (maszyna "nie ma czasu" żeby zapisać więcej komórek), oraz że złożenie dwóch wielomianów daje w efekcie wielomian. Własności te sprawiają, że ostateczny program będzie miał wielomianową złożoność, a co za tym idzie problem $L_1$ będzie należał do klasy $NP$.

Redukcje logarytmiczne

Drugą ciekawą rodziną redukcji jest rodzina redukcji logarytmicznych. Aby zdefiniować tą rodzinę zmodyfikujemy definicję maszyny Turinga - otóż wyznaczamy na niej dwie specjalne taśmy - wejściową (tylko do odczytu, tak jak przy maszynie off-line) i wyjściową. Po zapisie na taśmę wyjściową głowica przesuwa się zawsze w tym samym kierunku, co uniemożliwia odczyt poprzednio zapisanych symboli.

Powróćmy teraz do redukcji. Redukcja logarytmiczna jest funkcją obliczalną na deterministycznej maszynie Turinga z użyciem logarytmicznej ilości pamięci na taśmie roboczej. Zauważmy, że nie nakładamy żadnych ograniczeń na wielkość słowa wyjściowego - najczęśniej jego wielkość będzie wielomianowo zależna od wielkości słowa wejściowego. Intuicyjnie transformacja logarytmiczna pozwala przechowywać na taśmie roboczej stałą liczbę wskaźników do komórek wejściowych (lub innych obiektów o podobnej wielkości).

Ćwiczenie 2

Czy problem maksymalnego skojarzenia w grafie dwudzielnym jest redukowalny do problemu maksymalnego przepływu w sensie rodziny transformacji logarytmicznych?

Wskazówka

Prześledź, jakie dane muszą się znajdować w pamięci (czyli na taśmie roboczej) maszyny Turinga, wykonującej transformację.

Rozwiązanie

Załóżmy, że graf dwudzielny jest przedstawiony w postaci macierzy sąsiedztwa (niekoniecznie kwadratowej - w końcu wiemy, że graf wejściowy jest dwudzielny), oraz że na wyjście chcemy również wypisać graf w postaci macierzy sąsiedztwa (tym razem już kwadratowej). Problem ten możemy rozwiązać używając następujących danych na taśmie tymczasowej:

• dwie liczby reprezentujące pozycję aktualnie wypisywanego elementu macierzy wyjściowej (każda o rozmiarze logarytmicznie zależnym od wielkości wejścia),

• liczbę pamiętającą aktualną pozycję głowicy na taśmie wejściowej (rozmiar j.w.).

Aby wypisać jakiś element macierzy wyjściowej musimy sprawdzić, jakiego typu są odpowiadające mu wierzchołki, czyli czy są one: źródłem, ujściem, elementem pierwszego zbioru czy elementem drugiego zbioru. Taka klasyfikacja może zostać wykonana z użyciem logarytmicznej ilości pamięci (polega ona na wykonaniu kilku porównań liczb o rozmiarze logarytmicznym). Jeżeli okaże się, że element macierzy reprezentuje krawędź pomiędzy rozłącznymi zbiorami grafu dwudzielnego, to będziemy musieli odwołać się do grafu wejściowego. W tym celu będziemy musieli obliczyć numer komórki na taśmie wejściowej, która reprezentuje interesującą nas krawędź; możemy to jednak zrobić z użyciem tylko takiej ilości pamięci, która jest potrzebna aby zapisać wynik. Pozostaje nam już tylko przesunąć się do odpowiedniej komórki - ta operacja nie wymaga już jednak żadnej dodatkowej pamięci.

Możemy zatem stwierdzić, że przedstawiona powyżej redukcja działa z użyciem logarytmicznej ilości pamięci; problem maksymalnego skojarzenia w grafie dwudzielnym jest zatem redukowalny do problemu maksymalnego przepływu w sensie redukcji logarytmicznej.

Ćwiczenie 3

Czy istnienie redukcji logarytmicznej z problemu $L_1$ do problemu $L_2$ implikuje istnienie redukcji wielomianowej z $L_1$ do $L_2$? Odpowiedź uzasadnij.

Wskazówka

Zastosuj podobne rozumowanie, jak przy porównywaniu klas $P$ i $L$.

Rozwiązanie

Można łatwo oszacować liczbę konfiguracji, w których znajduje się maszyna implementująca redukcję logarytmiczną; składa się na nią ilość pozycji, w których może się znajdować głowica taśmy wejściowej ($(O(n))$ - możemy bezpiecznie założyć, że maszyna nie przesuwa się "zbyt daleko poza wejście" na tej taśmie), liczba stanów oraz liczba różnych napisów, które mogą się znaleźć na taśmie roboczej ($2^{O(\log n)}=O(n^k)$, dla pewnej stałej $k$). Liczba konfiguracji tej maszyny jest zatem wielomianowo zależna od wielkości wejścia; czas działania maszyny implementującej redukcję (a zatem "niezapętlającej się") musi być więc co najwyżej wielomianowy w stosunku do wielkości wejścia.

Istnienie redukcji logarytmicznej pociąga zatem za sobą istnienie redukcji wielomianowej.

Warto się zastanowić czy prawdziwa jest następująca hipoteza:

Ta niewątpliwie cenna (o ile prawdziwa) hipoteza nie jest jednak tak oczywista jak poprzednio pokazywane analogiczne fakty dla transformacji wielomianowej i klas $P$ oraz $NP$. Problem przy "składaniu" dwóch maszyn - transformacji oraz maszyny rozwiązującej $L_2$ - tkwi w tym, że być może nie będziemy w stanie zapisac wyjścia transformacji (o potencjalnie wielomianowej wielkości) na taśmie roboczej.

Posłużymy się tutaj następującym trikiem: Uruchomimy maszynę rozwiązującą problem $L_2$; za każdym razem, gdy maszyna ta będzie chciała odwołać się do któregoś - dla ustalenia uwagi $i$-tego - bitu wejścia, na osobnej taśmie uruchomimy maszynę implementującą redukcję z $L_1$ do $L_2$. Maszyna ta nie będzie jednak wypisywać kolejnych symboli na wyjście, tylko inkrementować specjalnie utworzony licznik operacji wyjścia; w momencie, gdy wykonana zostanie $i$-ta operacja wyjścia, maszyna powróci do wykonywania programu rozwiązującego problem $L_2$, wykorzystująć symbol, który miał zostać wypisany na wyjście przez maszynę transformującą. Takie postępowanie wydaje się mało wydajne - tym niemniej na taśmach roboczych nigdy nie znajduje się większa niż logarytmiczna liczba symboli - a zatem otrzymujemy algorytm dla problemu $L_1$, wykorzystujący logarytmiczną ilośc symboli. Analogiczny argument można zastosować do pokazania, że rodzina transformacji logarytmicznych jest domknięta na składanie.

Transformacja wielomianowa w sensie Turinga

Definiowana tutaj transformacja będzie miała trochę inny charakter od dwóch poprzednich - w szczególności formalnie nie będzie ona redukcją. Do jej zdefiniowania będziemy potrzebować pojęcia maszyny z wyrocznią.

Definicja

Maszyna z wyrocznią $Q\subseteq \{0,1{\}}^{\star }$ jest wielotaśmową maszyną Turinga, z jedną wyróżnioną taśmą i trzema wyróżnionymi stanami $\{q_a,q_b,q_c\}$. Zachowanie maszyny różni się od zachowania zwykłej maszyny Turinga w następujący sposób: Przejście maszyny do stanu $q_a$ jest traktowane jako odwołanie do wyroczni $Q$. Jeżeli słowo aktualnie zapisane na wyróżnionej taśmie należy do języka $Q$, to maszyna przechodzi do stanu $q_b$; w przeciwnym razie przechodzi do stanu $q_c$. Odwołanie do wyroczni wliczane jest do czasu działania maszyny jako jedno przejście.

Mówiąc nieformalnie maszyna może w trakcie działania wielokrotnie prosić wyrocznię o rozwiązanie problemu $Q$.

Definicja

Niech $L_1$ i $L_2$ będą językami nad alfabetem $\{0,1\}$. Mówimy, że $L_1$ transformuje się do $L_2$ w sensie wielomianowej transformacji Turinga wtedy i tylko wtedy gdy istnieje maszyna Turinga z wyrocznią $L_2$ rozwiązująca $L_1$ w czasie wielomianowym.

Transformacja Turinga intuicyjnie odpowiada stosowaniu podprogramów - jeżeli znamy rozwiązanie problemu $L_2$ to stosujemy go jako podprocedurę przy rozwiązywaniu problemu $L_1$.

Ćwiczenie 4

Niech $L_1$ i $L_2$ będą językami nad alfabetem $\{0,1\}$ oraz niech $L_1$ transformuje się do $L_2$ w sensie transformacji wielomianowej Turinga. Które z poniższych zdań jest prawdziwe:

• $L_1\in P\Rightarrow L_2\in P$,

• $L_2\in P\Rightarrow L_1\in P$?

Rozwiązanie

Po pierwsze należy zauważyć, że transformacja z problemu $L_1$ do $L_2$ nie mówi nam absolutnie nic o złożoności problemu $L_2$. Dodatkowo jeśli $L_1\in P$ to problem ten transformuje się w sensie Turinga do każdego problemu decyzyjnego (czyli np. do problemu trywialnego, albo problemu podwójnie wykładniczego) - można rozwiązać ten problem w ogóle nie odwołując się do wyroczni.

Druga implikacja oczywiście zachodzi. Problem $L_1$ można rozwiązać stosując rozwiązanie problemu $L_2$ jako subrutynę. Złożoność czasowa tego rozwiązania będzie określona od góry przez złożenie dwóch wielomianów - co jak wiemy również jest wielomianem.

Niniejsze ćwiczenie ma za zadanie zaprezentowanie pewnego częstego błędu logicznego; zazwyczaj bowiem jeśli myślimy o subrutynie, to traktujemy ją jako coś prostszego od całego problemu. W tej sytuacji jednak -- gdy mamy wielomianowy (czyli "prosty") algorytm używający pewnej subrutyny -- widzimy, że jedyna trudność w rozwiązywaniu danego problemu może tkwić w "trudności" tej właśnie subrutyny.

Łatwo zauważyć, że transformacja wielomianowa w sensie Turinga wyznacza preporządek na językach zawartych w $\{0,1{\}}^{\star }$. Oznaczamy ją symbolem ${\le }_T$.

Ćwiczenie 5

Które z poniższych zdań jest prawdziwe:

• $L_1{\le }_T{L}_2\Rightarrow L_1{\le }_P{L}_2$,

• $L_1{\le }_P{L}_2\Rightarrow L_1{\le }_T{L}_2$?

Rozwiązanie

Udowodnienie prawdziwości drugiego zdania jest natychmiastowe - wystarczy na maszynie z wyrocznią wykonać redukcję wielomianową (w sensie Karpa), po czym odwołać się do wyroczni i w zależności od jej odpowiedzi przejść do stanu akceptującego lub odrzucającego.

Pierwsze zdanie nie jest prawdziwe; zauważyliśmy wcześniej, że problemy z $P$ są redukowalne w sensie Turinga do każdego problemu - w szczególności do problemu reprezentowanego przez język pusty. Łatwo zauważyć, że nietrywialnych - to znaczy nie reprezentowanych przez język pusty ani pełny - problemów z klasy $P$ nie da się zredukować w sensie transformacji wielomianowej Karpa do problemu reprezentowanego przez język pusty; maszyna akceptująca ten język nigdy nie da odpowiedzi 'tak'.

Widać, że powyższy dowód stosuje pewien "kruczek" w definicji redukcji; jeżeli założymy, że język $L_2$ nie może być pusty ani pełny, to prawdziwość pierwszego zdania będzie problemem otwartym.