|
|
| (Nie pokazano 8 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>
| |
|
| |
| ===Zupełność===
| |
|
| |
| Zastosujemy teraz zdefiniowane uprzednio rodziny transformacji do zdefiniowania
| |
| dla wybranych klas złożoności ich najbardziej reprezentatywnych przedstawicieli
| |
| - swoistej arystokracji w ramach danej klasy.
| |
|
| |
| {{definicja|||
| |
| Niech <math>\mathcal C</math> będzie pewną klasą złożoności, natomiast <math>\sqsubseteq</math> preporządkiem określonym na językach zawartych w <math>\{ 0, 1 \} ^\star</math> (w domyśle jedną ze zdefiniowanych wcześniej rodzin transformacji). Mówimy, że problem decyzyjny <math>L \subseteq \{ 0, 1 \} ^\star</math> jest <math>\mathcal C</math>-zupełny w sensie preporządku <math>\sqsubseteq</math> wtedy i tylko wtedy, gdy:
| |
|
| |
| *<math>L \in {\mathcal C}</math>,
| |
|
| |
| *<math>\forall_{L' \in \mathcal C} L' \sqsubseteq L</math>.
| |
| }}
| |
|
| |
| Intuicyjnie problem <math>\mathcal C</math>-zupełny jest najtrudniejszym do rozwiązania problemem w klasie złożoności <math>{\mathcal C}</math>. Warto zauważyć, że może istnieć (i zazwyczaj istnieje) więcej niż jeden problem <math>{\mathcal C}</math>-zupełny. Problemy te są równoważne w sensie relacji preporządku <math>\sqsubseteq</math>.
| |
|
| |
| {{cwiczenie|6||
| |
| Scharakteryzuj problemy <math>P</math>-zupełne w sensie transformacji wielomianowej.
| |
| }}
| |
|
| |
| <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"> Problemami <math>P</math>-zupełnymi są wszystkie problemy reprezentowane przez nietrywialne (to znaczy nie-puste i nie-pełne) języki. Transformacja języka <math>L_1 \in P</math> do nietrywialnego języka <math>L_2 \in P</math> będzie tutaj polegała na rozwiązaniu problemu <math>L_1</math>, a następnie - w zależności czy obliczenie jest akceptujące czy nie - na wypisaniu jednej z dwóch ustalonych wcześniej instancji problemu <math>L_2</math>, z których pierwsza należy a druga nie należy do <math>L_2</math>.
| |
|
| |
| </div></div>
| |
|
| |
| Jak zauważyliśmy rozpatrywana powyżej klasa jest mało interesująca. Jeszcze
| |
| mniej interesująca jest oczywiście klasa problemów <math>P</math>-zupełnych w sensie transformacji wielomianowej Turinga. Dla odróżnienia - klasa problemów
| |
| <math>P</math>-zupełnych w sensie transformacji logarytmicznej cieszy się niemałym zainteresowanie specjalistów z dziedziny złożoności obliczeniowej; z tego powodu najczęściej określa się ją po prostu jako klasę problemów <math>P</math>-zupełnych.
| |
|
| |
| {{uwaga|[na marginesie]||
| |
| Przykładem problemu <math>P</math>-zupełnego jest problem HORNSAT. Jego opis można znaleźć w ...
| |
| }}
| |
|
| |
| ===Klasa NP i NP-zupełność===
| |
|
| |
| W ramach tego kursu naszym największym zainteresowaniem będzie się cieszyć klasa
| |
| <math>NP</math>, a w szczególności problemy <math>NP</math>-zipełne w sensie trzech poznanych wcześniej rodzin transformacji. Zanim jednak przejdziemy do problemów <math>NP</math>-zupełnych, poznamy pewną alternatywną definicję klasy złożoności <math>NP</math>.
| |
|
| |
| {{twierdzenie|||
| |
| Niech <math>L \subseteq \{ 0, 1 \} ^\star</math>. Wtedy:
| |
|
| |
| <center><math>
| |
| L \in NP \iff \exists_{p(x)-wielomian} \exists_{L' \in P}
| |
| \forall_{n \in {\mathbb N}} \forall_{w \in \{ 0, 1 \} ^n}
| |
| [w \in L \iff (\exists_{v \in \{ 0, 1 \}^{p(n)}} \langle w, v \rangle \in L')
| |
| ]</math>
| |
| </center>
| |
| }}
| |
|
| |
| Zanim udowodnimy powyższy fakt, spróbujmy najpierw prześledzić, co się
| |
| właściwie dzieje po prawej stronie równoważności. Słowo <math>v</math> zwykle nazywane jest ''świadkiem'' (ang. ''witness'') słowa <math>w</math>. Żądamy, żeby każde słowo należące do języka <math>L</math> miało świadka o długości wielomianowej, natomiast żadne słowo spoza <math>L</math> takiego świadka nie miało. Co więcej - żądamy, aby sprawdzanie, czy <math>v</math> jest świadkiem słowa <math>w</math> było wykonywane w czasie wielomianowym na maszynie deterministycznej - dlatego klasę <math>NP</math> czasem nazywamy klasą problemów weryfikowalnych w czasie wielomianowym.
| |
|
| |
| {{przyklad|[<math>NONPRIME</math>]||
| |
| Rozważmy problem <math>NONPRIME</math>. Niech <math>w \in \{ 0, 1 \} ^\star</math> będzie reprezentacją liczby naturalnej w systemie binarnym.
| |
|
| |
| <math>w \in NONPRIME \iff</math> liczba reprezentowana przez <math>w</math> nie jest liczbą pierwszą
| |
|
| |
| Aby pokazać, że liczba nie jest pierwsza, wystarczy podać dowolny jej nietrywialny dzielnik (nie dotyczy to oczywiście liczby 1). Właśnie ten dzielnik będzie naszym świadkiem (w specjalnym przypadku liczby 1 uznamy, że jej świadkiem jest 1). Język <math>L'</math> będzie miał wtedy następującą postać:
| |
|
| |
| <math>L' := \{ \langle w, v \rangle: (num(v) \neq num(w) \wedge num(v) \neq 1 \wedge num(v) \mid num(w)) \vee num(w) = num(v) = 1 \}</math>
| |
|
| |
| gdzie <math>num(v)</math> oznacza liczbę reprezentowaną przez słowo <math>v</math>. Łatwo zauważyć, że <math>L'</math> jest implementowalna w czasie wielomianowym na deterministycznej maszynie - wystarczy pisemnie podzielić <math>w</math> przez <math>v</math>, sprawdzić, czy zostanie reszta z dzielenia i ewentualnie obsłużyć przypadek brzegowy (liczbę 1). Zatem jak tylko udowodnimy powyższe twierdzenie, będziemy mogli stwierdzić, że <math>NONPRIME \in NP</math>.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| W stronę <math>\Leftarrow</math> dowód jest prosty - skonstruujemy niedeterministyczną maszynę Turinga, rozwiązującą problem <math>L</math>. Maszyna ta najpierw przesunie głowicę za słowo wejściowe, przez następne <math>p(n)</math> kroków będzie wypisywać na taśmę symbole 0 lub 1 (tu jest stosowany niedeterminizm) i przesuwać głowicę w prawo. Od tej pory maszyna będzie działać całkowicie deterministycznie - przesunie się na początek taśmy i zacznie się zachowywać jak deterministyczna maszyna rozwiązująca problem <math>L'</math> w czasie wielomianowym.
| |
|
| |
| Jeżeli dla słowa wejściowego <math>w</math> istnieje świadek, to zostanie on wygenerowany przez jedną ze ścieżek postępowania w etapie niedeterministycznym. W przeciwnym przypadku wszyscy "kandydaci na świadków" zostaną odrzuceni (''zdemaskowani'') przez maszynę rozwiązującą <math>L'</math>.
| |
|
| |
| Udowodnijmy teraz przejście w drugą stronę (<math>\Rightarrow</math>). Skoro <math>L \in NP</math> to istnieje niedeterministyczna maszyna Turinga - <math>M</math> - rozstrzygająca problem <math>L</math>. Niech <math>k</math> oznacza ''maksymalny stopień rozgałęzienia'' maszyny <math>M</math>, tj.
| |
|
| |
| <math>k := \max_{(s, q) \in \Sigma \times Q} \# d(s, q)
| |
| </math>
| |
|
| |
| czyli mówiąc nieformalnie największą liczbę rozgałęzień, która może się dokonać
| |
| w jednym kroku. Łatwo zauważyć, że istnieje równoważna maszyna <math>M'</math> co najwyżej <math>k-1</math>-krotnie wolniejsza (a zatem nadal wielomianowa) o maksymalnym stopniu rozgałęzienia równym 2 - uzasadnienie przedstawione jest na
| |
| poniższym rysunku.
| |
|
| |
| [[ZO-4-2. Przekształcanie rozgałęzienia stopnia <math>k</math> w <math>k-1</math> rozgałęzień stopnia 2.]]
| |
|
| |
| Od tej pory będziemy się zajmować maszyną <math>M'</math>. Oznaczmy jej czas działania jako <math>W(n)</math>; w związku z tym maszyna dla słowa wielkości <math>n</math> wykona co najwyżej <math>W(n)</math> rozgałęzień. Każda ścieżka postępowania maszyny <math>M'</math> jest zatem zdefiniowana poprzez ciąg <math>W(n)</math> bitów mówiących, którą spośród co najwyżej dwóch dostępnych ścieżek została wybrana. Jako "kandydatów na świadków" wybierzmy zatem ciągi <math>\{ 0, 1 \} ^{W(n)}</math>, świadkiem natomiast niech będzie ciąg reprezentujący akceptującą ścieżkę postępowania maszyny <math>M'</math> - o ile
| |
| taka istnieje.
| |
|
| |
| Wystarczy w tym momencie wksazać deterministyczna maszynę Turinga <math>N</math>, rozpoznającą język <math>L'</math> - czyli weryfikującą dla pary słów <math>\langle w, v \rangle</math> czy <math>v</math> jest świadkiem dla <math>w</math>. Maszyna taka jest prosta do skonstruowania w następujący sposób:
| |
|
| |
| *<math>N</math> najpierw przepisuje <math>v</math> na tasmę pomocniczą, po czym wraca na głównej taśmie do początku słowa <math>w</math>,
| |
|
| |
| *<math>N</math> zachowuje się podobnie jak maszyna <math>M'</math>; w przypadku, gdy maszyna ma do wyboru dwie opcje, <math>N</math> sięga po kolejny dostępny bit taśmy pomocniczej i na jego podstawie wybiera ścieżkę postępowania.
| |
| Łatwo zauważyc, że <math>M'</math> akceptuje słowo <math>w</math> wtedy i tylko wtedy gdy istnieje świadek, który spowoduje że maszyna <math>N</math> dojdzie do stanu akceptującego.
| |
| }}
| |
|
| |
| Poznaliśmy zatem alternatywna definicję klasy <math>NP</math>. Potocznie często mówi się, że maszyna rozwiązująca problem z klasy <math>NP</math> najpierw "zgaduje" świadka, a potem weryfikuje go w deterministyczny sposób w czasie wielomianowym. Należy jednak pamiętać, że maszyna w rzeczywistości nie "zgaduje" - zamiast tego sprawdza ona ''wszystkich'' możliwych świadków.
| |
|
| |
| Powrócmy teraz do redukcji i problemów zupełnych. Oznaczmy jako <math>NPC</math>, <math>NPC_L</math> i <math>NPC_T</math> klasy problemów <math>NP</math>-zupełnych w sensie odpowiednio transformacji wielomianowej Karpa, transformacji logarytmicznej i transformacji wielomianowej Turinga. W tym momencie w żaden sposób nie uzasadniliśmy jeszcze, dlaczego którakolwiek z tych klas miałaby być niepusta. Mimo to już w tym momencie można okreslić pewne relacje zawierania pomiędzy tymi klasami.
| |
|
| |
| {{cwiczenie|7||
| |
| Uszereguj klasy <math>NPC</math>, <math>NPC_L</math> i <math>NPC_T</math> od najwęższej do najszerszej i uzasadnij to uszeregowanie.
| |
| }}
| |
|
| |
| <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"> Prawdziwe są następujące zawierania:
| |
|
| |
| <math>NPC_L \subseteq NPC \subseteq NPC_T</math>
| |
|
| |
| Weźmy dowolny problem z <math>NPC_L</math>. Wiemy, że można do niego przekształcić każdy problem z <math>NP</math> z użyciem transformacji logarytmicznej. Na podstawie udowodnionych wcześniej faktów wiemy jednak, że redukowalność logarytmiczna implikuje redukowalność wielomianową; rozpatrywany problem należy zatem do klasy <math>NPC</math>. Analogiczne rozumowanie można zastosować do uzasadnienia drugiej inkluzji.
| |
|
| |
| Nie wiadomo czy pomiędzy jakąś parą klas zachodzi równość.
| |
| </div></div>
| |
|
| |
| '''Problem SAT'''
| |
|
| |
| Zdefiniowanie problemu <math>SAT</math> wymaga uprzedniego wprowadzenia (względnieprzypomnienia) kilku pojęć z dziedziny logiki:
| |
|
| |
| * ''literałem'' nazywamy zmienną lub jej zaprzeczenie,
| |
|
| |
| * ''klauzulą'' nazywamy alternatywę skończonej liczby literałów,
| |
|
| |
| *mówimy, że formuła logiczna jest w ''koniunkcyjnej postaci normalnej'' wtedy i tylko wtedy gdy jest koniunkcją skończonej liczby klauzul. Przykładem formuły w koniunkcyjnej postaci normalnej jest formuła:
| |
|
| |
| <math>(x_1 \vee x_2 \vee \neg x_3) \wedge (x_2 \vee x_3) \wedge (\neg x_1 \vee \neg x_4)</math>
| |
|
| |
| Mówimy, że formuła jest spełnialna wtedy i tylko wtedy gdy istnieje wartościowanie zmiennych, dla których ta formuła jest spełniona. Dla powyższej formuły jednym z wartościowań, dla których jest ona spełniona, jest wartościowanie przypisujące zmiennym <math>x_1</math>, <math>x_2</math>, <math>x_3</math>, <math>x_4</math> odpowiednio wartości 0, 1, 1, 0; w związku
| |
| z tym powyższa formuła jest spełnialna.
| |
|
| |
| Do dalszych rozważań ustalmy pewne kodowanie formuł logicznych do słów nad
| |
| alfabetem <math>\{ 0, 1\}</math> - na przykład ustalmy, że najpierw zapisujemy liczbę klauzul, następnie dla każdej klauzuli liczbę literałów, a następnie dla
| |
| każdego literału numer zmiennej oraz bit określający czy zmienna jest zaprzeczona.
| |
|
| |
| {{definicja|||
| |
| Niech <math>w \in \{ 0, 1 \} ^\star</math>. Wtedy
| |
|
| |
| <math>w \in SAT \iffw</math> reprezentuje poprawnie zakodowaną formułę logiczną w koniunkcyjnej postaci normalnej i formuła ta jest spelnialna.
| |
|
| |
| }}
| |
|
| |
| {{cwiczenie|8||
| |
| Pokaż, że problem <math>SAT</math> 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">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> Wykorzystaj definicję klasy <math>NP</math> wykorzystującą świadka.
| |
| </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"> Jak się okazuje problem <math>SAT</math> jest problemem <math>NP</math>-zupełnym w sensie redukcji
| |
| logarytmicznej (a co za tym idzie również w sensie pozostałych dwóch znanych
| |
| nam typów transformacji). Odpowiednie twierdzenie zostało udowodnione w
| |
| roku 1971 niezależnie przez Stephena Cook'a i Leonida Lewina.
| |
| </div></div>
| |
