|
|
| (Nie pokazano 11 wersji utworzonych przez 2 użytkowników) |
| Linia 1: |
Linia 1: |
| ==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 <math>\mathcal F</math> będzie pewną rodziną funkcji o sygnaturze
| |
|
| |
| <math>\{ 0, 1 \} ^{\star} \rightarrow \{ 0, 1 \} ^{\star}</math>
| |
|
| |
|
| |
| domkniętą na składanie i zawierającą identyczność. Niech <math>L_1</math> i <math>L_2</math> będą językami nad alfabetem <math>\{ 0, 1 \}</math> (czyli inaczej mówiąc zakodowanymi binarnie problemami decyzyjnymi). Mówimy, że problem <math>L_1</math> jest redukowalny do problemu <math>L_2</math> w sensie rodziny <math>\mathcal F</math> i zapisujemy
| |
|
| |
| <math>L_1 \leq_{\mathcal F} L_2</math>
| |
|
| |
| wtedy i tylko wtedy, gdy
| |
|
| |
| <math>\exists_{f \in \mathcal F} \forall_{w \in \{ 0, 1 \} ^\star}
| |
| w \in L_1 \iff f(w) \in L_2</math>
| |
|
| |
| }}
| |
|
| |
| Intuicyjnie problem <math>L_1</math> jest w pewnym sensie co najwyżej tak trudny jak problem <math>L_2</math> - jeżeli znamy rozwiązanie problemu <math>L_2</math> oraz odpowiednią funkcję (zwaną redukcją lub transformacją), to znamy również rozwiązanie problemu <math>L_1</math>. Warto zauważyć, że relacja <math>\leq_{\mathcal F}</math> jest preporządkiem, to znaczy jest zwrotna (ze względu na obecność identyczności) i przechodnia (ze względu na domkniętość rodziny <math>\mathcal F</math> na składanie).
| |
|
| |
| Przedstawmy teraz najczęściej stosowane rodziny redukcji.
| |
|
| |
| '''Redukcje wielomianowe'''
| |
|
| |
| Rodzina redukcji wielomianowych (Karpa) to rodzina funkcji <math>\{ 0, 1 \} ^{\star} \rightarrow \{ 0, 1 \} ^{\star}</math> 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 <math>L_1</math> jest redukowalny wielomianowo do problemu <math>L_2</math> oraz <math>L_2</math> należy do klasy <math>P</math>, to <math>L_1</math> również należy do klasy <math>P</math>. Aby uzasadnić tą własność wystarczy skonstruować maszynę, która najpierw przekształci instancję problemu <math>L_1</math> do instancji problemu <math>L_2</math> (uczyni to w czasie wielomianowym, bo <math>L_1</math> jest
| |
| wielomianowo redukowalne do <math>L_2</math>), po czym w czasie wielomianowym da odpowiedź dla instancji problemu <math>L_2</math>.
| |
|
| |
| {{cwiczenie|1||
| |
| Załóżmy, że <math>L_1</math> jest wielomianowo redukowalne do <math>L_2</math> oraz <math>L_2</math> należy do klasy <math>NP</math>. Pokaż, że <math>L_1</math> również należy do klasy <math>NP</math>.
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 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 <math>L_1</math> do <math>L_2</math>, po czym uruchomić niedeterministyczną maszynę, rozwiązującą problem <math>L_2</math> w czasie wielomianowym. Otrzymamy w tym momencie niedeterministyczną maszynę rozwiązującą problem <math>L_1</math>. 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 <math>L_1</math> będzie należał do klasy <math>NP</math>.
| |
| </div></div>
| |
|
| |
| '''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).
| |
|
| |
| {{cwiczenie|2||
| |
| Czy problem maksymalnego skojarzenia w grafie dwudzielnym jest redukowalny
| |
| do problemu maksymalnego przepływu w sensie rodziny transformacji
| |
| logarytmicznych?
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Prześledź, jakie dane muszą się znajdować w pamięci (czyli na taśmie roboczej) maszyny Turinga, wykonującej transformację.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 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.
| |
| </div></div>
| |
|
| |
| {{cwiczenie|3||
| |
| Czy istnienie redukcji logarytmicznej z problemu <math>L_1</math> do problemu <math>L_2</math> implikuje istnienie redukcji wielomianowej z <math>L_1</math> do <math>L_2</math>? Odpowiedź uzasadnij.
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Zastosuj podobne rozumowanie, jak przy porównywaniu klas <math>P</math> i <math>L</math>.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 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 (<math>(O(n))</math> - 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 (<math>2^{O(\log n)} = O(n^k)</math>, dla pewnej stałej <math>k</math>). 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.
| |
| </div></div>
| |
|
| |
| Warto się zastanowić czy prawdziwa jest następująca hipoteza:
| |
|
| |
| {{hipoteza|||
| |
| Niech <math>L_1 \leq_L L_2</math> i <math>L_2 \in L</math>. Wtedy <math>L_1 \in L</math>.
| |
| }}
| |
|
| |
| Ta niewątpliwie cenna (o ile prawdziwa) hipoteza nie jest jednak tak oczywista
| |
| jak poprzednio pokazywane analogiczne fakty dla transformacji wielomianowej
| |
| i klas <math>P</math> oraz <math>NP</math>. Problem przy "składaniu" dwóch maszyn - transformacji oraz maszyny rozwiązującej <math>L_2</math> - 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 <math>L_2</math>; za każdym razem, gdy maszyna ta będzie chciała odwołać się do któregoś - dla ustalenia uwagi <math>i</math>-tego - bitu wejścia, na osobnej taśmie uruchomimy maszynę implementującą redukcję z <math>L_1</math> do <math>L_2</math>. 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 <math>i</math>-ta operacja wyjścia, maszyna powróci do wykonywania programu rozwiązującego problem <math>L_2</math>, 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 <math>L_1</math>, 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ą <math>Q \subseteq \{ 0, 1 \} ^\star</math> jest wielotaśmową
| |
| maszyną Turinga, z jedną wyróżnioną taśmą i trzema wyróżnionymi stanami <math>\{ q_a, q_b, q_c \}</math>. Zachowanie maszyny różni się od zachowania zwykłej maszyny Turinga w następujący sposób: Przejście maszyny do stanu <math>q_a</math> jest traktowane jako odwołanie do wyroczni <math>Q</math>. Jeżeli słowo aktualnie zapisane na wyróżnionej taśmie należy do języka <math>Q</math>, to maszyna przechodzi do stanu <math>q_b</math>; w przeciwnym razie przechodzi do stanu <math>q_c</math>. 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 <math>Q</math>.
| |
|
| |
| {{definicja|||
| |
| Niech <math>L_1</math> i <math>L_2</math> będą językami nad alfabetem <math>\{ 0, 1 \}</math>. Mówimy, że <math>L_1</math> transformuje się do <math>L_2</math> w sensie wielomianowej transformacji Turinga wtedy i tylko wtedy gdy istnieje maszyna Turinga z wyrocznią <math>L_2</math> rozwiązująca <math>L_1</math> w czasie wielomianowym.
| |
| }}
| |
|
| |
| Transformacja Turinga intuicyjnie odpowiada stosowaniu podprogramów - jeżeli znamy rozwiązanie problemu <math>L_2</math> to stosujemy go jako podprocedurę
| |
| przy rozwiązywaniu problemu <math>L_1</math>.
| |
|
| |
| {{cwiczenie|4||
| |
| Niech <math>L_1</math> i <math>L_2</math> będą językami nad alfabetem <math>\{ 0, 1 \}</math> oraz niech <math>L_1</math> transformuje się do <math>L_2</math> w sensie transformacji wielomianowej Turinga. Które z poniższych zdań jest prawdziwe:
| |
|
| |
| *<math>L_1 \in P \Rightarrow L_2 \in P</math>,
| |
|
| |
| *<math>L_2 \in P \Rightarrow L_1 \in P</math>?
| |
|
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> Po pierwsze należy zauważyć, że transformacja z problemu <math>L_1</math> do <math>L_2</math> nie mówi nam absolutnie nic o złożoności problemu <math>L_2</math>. Dodatkowo jeśli <math>L_1 \in P</math> 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 <math>L_1</math> można rozwiązać stosując rozwiązanie problemu <math>L_2</math> 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.
| |
| </div></div>
| |
|
| |
| Łatwo zauważyć, że transformacja wielomianowa w sensie Turinga wyznacza
| |
| preporządek na językach zawartych w <math>\{ 0, 1 \} ^\star</math>. Oznaczamy ją
| |
| symbolem <math>\leq_T</math>.
| |
|
| |
| {{cwiczenie|5||
| |
| Które z poniższych zdań jest prawdziwe:
| |
|
| |
| *<math>L_1 \leq_T L_2 \Rightarrow L_1 \leq_P L_2</math>,
| |
|
| |
| *<math>L_1 \leq_P L_2 \Rightarrow L_1 \leq_T L_2</math>?
| |
|
| |
| }}
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"> 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 <math>P</math> 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 <math>P</math> 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 <math>L_2</math> nie może być pusty ani pełny, to prawdziwość pierwszego
| |
| zdania będzie problemem otwartym.
| |
| </div></div>
| |
