|
|
| (Nie pokazano 11 wersji utworzonych przez 2 użytkowników) |
| Linia 1: |
Linia 1: |
| ==Wstęp==
| |
|
| |
|
| Jak czytelnikowi wiadomo, w aktualnym stanie wiedzy NP-zupełność
| |
| jest podstawowym narzędziem do badania probelu algorytmicznego pod
| |
| kątem jego trudności obliczeniowej. Na tym wykładzie dla wielu
| |
| znanych klasycznych problemów z teorii grafów, kombinatoryki, logiki
| |
| i innych podajemy definicje ich decyzyjnych wersji i wykazujemy ich
| |
| NP-zupełność. Z problematyką ta spotkaliśmy się już na kursie ''Algorytmy i struktury danych''. Tutaj rozbudowujemy te wiadomości,
| |
| czynimy je bardziej formalnymi posługując się modelem maszyny
| |
| Turinga i redukcją logarytmiczną. Na przedstawionych przykładach
| |
| omawiamy również techniki dowodzenia NP-zupełności. Następny wykład
| |
| pokazuje wykorzystanie tych technik do analizy złożoności problemu i
| |
| jego zawężeń.
| |
|
| |
| ==O problemie SAT==
| |
|
| |
| Aby wykazać, że dany problem <math>Q</math> z klasy NP jest NP-zupełny, zgodnie
| |
| z własnościami redukcji logarytmicznej (przechodniość) wystarcza
| |
| pokazać, dla dowolnego problemu <math>Q' \in NPC</math>, że <math>Q'</math> redukuje się
| |
| do <math>Q</math>. Innymi słowy, proces dowodzenia że dany problem <math>Q</math> jest w
| |
| NPC składa sie z nastepujących kroków:
| |
| * dowieść że <math>Q</math> należy do NP
| |
|
| |
| * wybrać znany problem NP-zupełny <math>Q'</math> i skonstruować redukcję z <math>Q'</math> do <math>Q</math>.
| |
|
| |
| Przypomnijemy, że redukcja z problemu A do B dowodzi, że B jest
| |
| niełatwiejszy niż A. Zatem dla konstrukcji takiej redukcji łatwiej
| |
| jest, gdy (są to rozważania czysto intuicyjne):
| |
| * problem A nie jest skomplikowany, tzn. instancje tego problemu
| |
| wykazują pewną regularność, łatwą do "opisu" lub "zmierzenia"
| |
|
| |
| * problem B dopuszcza konstrukcje różnorodnych instancji, jest "bogaty
| |
| strukturalnie"
| |
|
| |
| Stąd dla wypracowania sobie "warsztatu" dla konstruowania dowodów
| |
| NP-zupełności warto rozpocząć od dowiedzenia tej własności dla kilku
| |
| nieskomplikowanych (pod wzgledem opisu struktury) problemów. W
| |
| rzeczywistości, w literaturze dotyczącej tych zagadnień, można
| |
| wyodrębnić niewielką grupę klasycznych w tym sensie problemów, które
| |
| najczęściej wystepują jako lewa strona redukcji w dowodach
| |
| NP-zupełnosci. Poniżej definiujemy lub przypominamy grupe takich
| |
| problemów, dość różnorodnego pochodzenia i zastosowania, i dowodzimy
| |
| ich NP-zupełności.
| |
|
| |
| ===Najpierw 3SAT===
| |
|
| |
| Zaczynamy od sytuacji, w której jedynym znanym problemem NP-zupełnym
| |
| (a więc możliwą lewą stroną redukcji) jest problem SAT. Jest on dość
| |
| niewygodny jako problem źródłowy, redukcja z SAT do innego problemu
| |
| na ogół wymaga skomplikowanego opisu. Okazuje się (wykazał to już
| |
| Cook w swojej fundamentalnej pracy o NP-zupełności), że podproblem
| |
| problemu SAT, w którym wymagamy aby każda klauzula zawierała nie
| |
| więcej niz 3 literały jest sam w sobie NP-zupełny, a dowód tego
| |
| faktu jest dość łatwy.
| |
|
| |
| {{twierdzenie|||
| |
| Problem 3SAT jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Problem 3SAT, jako podproblem problemu w klasie NP, sam należy do
| |
| NP, zatem pierwsza część dowodu jest za nami.
| |
|
| |
| Konstruujemy redukcję z problemu SAT do 3SAT. Na wejściu mamy
| |
| formułe <math>\phi = C_1 \wedge \ldots \wedge C_m</math> nad zmiennymi
| |
| <math>x_1,\ldots,x_n</math>. Każdą z klauzul <math>C_j</math> przekształcamy osobno. Bez
| |
| straty ogólności załóżmy, że <math>C_j = x_1\vee\ldots\vee x_k</math>, gdzie
| |
| <math>x_i, i=1,\ldots,k</math> są parami różne. Jeśli <math>k\leq 3</math> to kładziemy
| |
| <math>D_j = C_j</math>.
| |
|
| |
| Niech <math>k>3</math>. Dodajemy <math>k-3</math> nowych zmiennych <math>y_2, \ldots, y_{k-2}</math>,
| |
| i zastepujemy <math>C_j</math> przez
| |
|
| |
|
| |
| <center><math>D_j = (x_1\vee x_2\vee y_2)\wedge( \neg y_2\vee x_3\vee y_3)\wedge
| |
| ( \neg y_3\vee x_4\vee y_4)\wedge ...
| |
| \wedge(\neg y_{k-2}\vee x_{k-1}\vee x_k)</math></center>
| |
|
| |
|
| |
| Nietrudno spostrzec, że jeśli <math>C_j</math> jest spełniona przez pewne
| |
| wartościowanie zmiennych <math>x_1,...,x_k</math>, to da się tak dobrać
| |
| wartości dla zmiennych <math>y_2,...,y_{k-2}</math>, aby spełnione były
| |
| wszystkie klauzule w <math>D_j</math>. Na odwrót, jeśli <math>D_j</math> jest spełniona
| |
| dla pewnego wartościowania zmiennych
| |
| <math>x_1,...,x_k,y_2,...,y_{k-2}</math>, to łatwo wydedukować, że
| |
| <math>x_i = 1</math> dla pewnego <math>1\leq i\leq k</math>. Mianowicie, jeśli <math>x_1=x_2 = 0</math>,
| |
| to z pierwszej klauzuli w <math>D_j</math> wynika że <math>y_2 = 1</math>. Ale wtedy z
| |
| drugiej klauzuli mamy <math>x_3=1</math> lub <math>y_3=1</math>. W pierwszym przypadku
| |
| rozumowanie jest zakończone, w drugim przenosimy rozumowanie na
| |
| trzecią klauzulę i tak dalej.
| |
|
| |
| Zatem, po przekształceniu kolejno wszystkich alternatyw powstaje
| |
| równoważna formuła o co najwyżej trójskładnikowych alternatywach.
| |
| Pozostaje wykazać, że przekształcenie to realizowalne jest w pamięci
| |
| logarytmicznej. Zauważmy jednak, że aby wypisać formułę wynikową, MT
| |
| potrzebuje pamięć roboczą tylko na licznik bieżącej alternatywy
| |
| <math>C_j</math> oraz licznik wygenerowanych do tej pory nowych zmiennych.
| |
| }}
| |
|
| |
| {{uwaga|1||
| |
| Zapewne zauważyłaś(-łeś), że w wielu podręcznikach do algorytmiki
| |
| również mówi się o NP-zupełności. Na ogół korzysta się wtedy z
| |
| redukcji wielomianowej. Złożoność czasowa jest łatwiejsza do analizy
| |
| w przypadku modelu obliczeń takiego jak (uproszczony) język
| |
| programowania wysokiego poziomu. Analiza złożoności pamięciowej (i
| |
| to tylko z uwzględnieniem pamięci roboczej) może być trudniejsza.
| |
|
| |
| Redukcja logarytmiczna jest bardziej uniwersalna i dlatego stosujemy
| |
| ją w teorii złożoności.
| |
| }}
| |
|
| |
| {{uwaga|2||
| |
| W literaturze przyjmuje sie również nieco inną definicję problemu
| |
| 3SAT, w której zakłada sie dodatkowo, że w każdej klauzuli występują
| |
| dokładnie 3 parami różne literały. Dowód NP-zupełności tej wersji
| |
| otrzymujemy przez uzupełnienie dowodu powyższego w następujący
| |
| sposób:
| |
|
| |
| Załóżmy że <math>k=2</math>. Wprowadzamy nową zmienną <math>y</math> i kładziemy <math>D_j =
| |
| (x_1\vee x_2\vee y)\wedge (x_1 \vee x_2 \vee \neg y)</math>. Jeśli
| |
| istnieje wartościowanie spełniające formułę <math>\phi</math>, to w tym
| |
| wartościowaniu formuła <math>\psi</math> powstała z <math>\phi</math> przez zastąpienie
| |
| klauzuli <math>C_j</math> formułą <math>D_j</math> jest również spełniona. I na odwrót,
| |
| jeśli pewne wartościowanie spełnia formułę <math>\psi</math>, to aby <math>D_j</math> było
| |
| prawdziwe <math>x_1</math> lub <math>x_2</math> musi mieć wartość 1, a zatem to samo
| |
| wartościowanie (bez zmiennej <math>y</math>) spełnia formułę <math>\phi </math>.
| |
|
| |
| Analogicznie, jesli <math>C_j</math> składa się tylko z jednego literału, to
| |
| przekształcamy go w koniunkcję czterech trójskładnikowych klauzul, z
| |
| dodanymi dwiema nowymi zmiennymi.
| |
|
| |
| Z tego spostrzeżenia będziemy korzystać w następnych dowodach
| |
| NP-zupełności.
| |
| }}
| |
|
| |
| Odnotujmy w tym miejscu, że dalsze zawężenie problemu polegające na
| |
| dopuszczeniu klauzul o co najwyżej dwóch literałach, 2SAT, jest
| |
| problemem obliczeniowo łatwym. Dowód tego faktu odkładamy do
| |
| nastepnej lekcji.
| |
|
| |
| ===MAXSAT===
| |
|
| |
| Warto wspomnieć o innych NP-zupełnych wersjach problemu
| |
| spełnialnosci. Na przykład, możemy zapytać o istnienie
| |
| wartościowania spełniającego co najmniej zadaną liczbe <math>k</math> klauzul
| |
| (a niekoniecznie wszystkie). Problem ten nosi nazwę MAXSAT, i jest
| |
| ogólniejszy niż SAT (a zatem jest również w NPC). Jego trudność
| |
| przejawia sie również w tym, że zawężenie do klauzul długości dwa w
| |
| przeciwieństwie do SAT, pozostawia ten problem trudnym.
| |
|
| |
| {{twierdzenie|[MAX2SAT]||
| |
| Problem MAX2SAT jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Konstruujemy redukcję z problemu 3SAT. Na wejściu mamy formułę
| |
| <math>\phi=C_1\vee ...\vee C_m</math>. Każdą klauzulę <math>C_j=a\vee b\vee c</math> przekształcamy w zbiór 10 klauzul, dla wygody rozważań podzielonych
| |
| na trzy grupy, następujacej postaci:
| |
|
| |
| # <math>(a)(b)(c)(z)</math>
| |
|
| |
| # <math>(\neg a\vee \neg b)(\neg b\vee \neg c)(\neg a\vee \neg c)</math>
| |
|
| |
| # <math>(a\vee \neg z)(b\vee \neg z)(c\vee \neg z)</math>
| |
|
| |
| Tych 10 klauzul ma następujace własności:
| |
|
| |
| # Jeśli <math>a=b=c=0</math>, to niezależnie od wartości zmiennej <math>z</math> co najwyżej 6 klauzul jest spełnionych.
| |
|
| |
| # Jeśli któryś z literałów <math>a</math>, <math>b</math> lub <math>c</math> jest równy 1, to
| |
| można dobrać wartość <math>z</math> tak, że 7 klauzul jest spełnionych. Można
| |
| sie o tym przekonać analizując wszystkie przypadki. Na przykład,
| |
| jeśli <math>a=1</math>, <math>b=c=0</math>, to kładziemy <math>z=0</math>; jeśli <math>a=b=1</math>, <math>c=0</math>, to
| |
| również kładziemy <math>z=0</math>, jeśli natomiast <math>a=b=c=1</math> to 7 klauzul jest
| |
| spełnionych gdy <math>z=1</math>.
| |
|
| |
| Pozostaje zdefiniować żądaną liczbę spełnionych klauzul w formule
| |
| wynikowej na <math>7m</math>. Z wymienionych własności wynika, że formuła
| |
| wynikowa posiada wartościowanie spełniające dokładnie <math>7m</math>
| |
| alternatyw wtedy i tylko wtedy gdy formuła wejściowa jest
| |
| spełnialna.
| |
|
| |
| Maszyna Turinga realizująca redukcję potrzebuje pamieci roboczej
| |
| jedynie na liczniki, zatem działa w pamięci logarytmicznej.
| |
| }}
| |
|
| |
| ==NP-zupełne problemy grafowe==
| |
|
| |
| ===Pokrycie wierzchołkowe===
| |
|
| |
| Pierwszym z serii problemów grafowych, dla których udowodnimy
| |
| NP-zupełność, jest problem pokrycia wierzchołkowego. Dla grafu
| |
| nieskierowanego <math>G=(V,E)</math> mówimy, że podzbiór <math>V'\subseteq V</math> jest
| |
| pokryciem wierzchołkowym, jeśli każda krawędź w G ma co najmniej
| |
| jeden z końców w zbiorze <math>V'</math>.
| |
|
| |
| {{Problem| NODE COVER||
| |
| ''Wejście:'' Graf nieskierowany <math>G=(V,E)</math>, liczba całkowita <math>k\leq|V|</math>
| |
|
| |
| ''Wyjście:'' TAK jeśli G ma pokrycie wierzchołkowe o liczności k,
| |
| NIE w przeciwnym przypadku.
| |
| }}
| |
| {{twierdzenie|[Problem NODE COVER]||
| |
| Problem NODE COVER jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Dla podanego podzbioru zbioru wierzchołków bardzo łatwo sprawdzić
| |
| czy stanowi on pokrycie, zatem <math> NODE COVER\in NP</math>.
| |
|
| |
| Redukujemy problem 3SAT do NODE COVER. Na wejściu mamy formułę
| |
| <math>\phi=C_1\wedge ... \wedge C_m</math>, i zgodnie z uwagą poczyniona przy
| |
| dowodzie NP-zupełności 3SAT zakładamy, że każda alternatywa <math>C_j</math>
| |
| zawiera dokładnie 3 różne literały. Konstruujemy graf następujący:
| |
| każde wystąpienie literału jest wierzchołkiem grafu, wystąpienia
| |
| wewnątrz jednej klauzuli tworzą trójkąt. Ponadto, dla każdej pary
| |
| literałów przeciwnych wystepujących w różnych klauzulach
| |
| odpowiadające im wierzchołki łączymy krawędzią. Na koniec, kładziemy
| |
| <math>k=2m</math>.
| |
|
| |
|
| |
| <center>[[rys_5_1.jpg(Redukcja 3SAT do NODE COVER)]]</center>
| |
|
| |
|
| |
| Teraz należy wykazać, że formuła wejsciowa jest spełnialna wtedy i
| |
| tylko wtedy gdy wygenerowany graf ma pokrycie wierzchołkowe o
| |
| liczności <math>k</math>. Z ograniczenia na wielkość pokrycia wynika, że z
| |
| każdego trójkąta do pokrycia muszą być wybrane dokładnie dwa
| |
| wierzchołki. Jeśli formuła jest spełnialna, to w każdym trójkącie
| |
| można wyróżnić jeden wierzchołek <math>v</math> odpowiadający literałowi
| |
| równemu 1. Do pokrycia wybieramy pozostałe dwa wierzchołki.
| |
| Pokrywają one wszystkie krawędzie trójkątów oraz wychodzące z tych
| |
| wierzchołków krawędzie między trójkątami. Każda pozostała krawędź,
| |
| wychodząca z wierzchołka <math>v</math>, prowadzi do pewnego wierzchołka <math>w</math>
| |
| odpowiadającego zaprzeczeniu literału wierzchołka <math>v</math>, zatem literał
| |
| wierzchołka <math>w</math> ma wartość zero i <math>w</math> jest wybrane do pokrycia w
| |
| trójkącie w którym występuje. Zatem krawędź <math>(v, w)</math> też jest
| |
| pokryta.
| |
|
| |
| W drugą stronę, załóżmy, że dane jest pokrycie. W każdym trójkącie,
| |
| dla wierzchołka który nie jest w pokryciu, ustawiamy wartość
| |
| odpowiedniej zmiennej tak aby literał w tym wierzchołku był równy 1.
| |
| Należy zauważyć że takie wartościowanie jest niesprzeczne. Wynika to
| |
| stąd, że przeciwne literały zawsze odpowiadają dwóm wierzchołkom z
| |
| różnych trójkątów połączonych krawędzią. Co najmniej jeden z tych
| |
| wierzchołków jest w pokryciu, a więc odpowiadający mu literał nie
| |
| bierze udziału w obliczaniu wartościowania.
| |
|
| |
| Zauważmy, że tak jak i poprzednio, do realizacji redukcji wystarczy
| |
| pamięć robocza rzędu <math>n</math>, co kończy dowód.
| |
| }}
| |
|
| |
|
| |
|
| |
| ===Cykl i ścieżka Hamiltona===
| |
|
| |
| {{Problem| HAMILTONIAN CYCLE||
| |
| ''Wejście:'' Graf nieskierowany <math>G=(V,E)</math>
| |
|
| |
| ''Wyjście:'' TAK jeśli <math>G</math> ma cykl Hamiltona, czyli cykl
| |
| przchodzący przez każdy wierzchołek dokładnie raz, NIE w przeciwnym
| |
| przypadku.
| |
| }}
| |
|
| |
| {{twierdzenie|[Cykl Hamiltona]||
| |
| CYKL HAMILTONA jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|||
| |
| Przynależnośc do klasy NP jest oczywista. Konstruujemy redukcje z
| |
| problemu NODE COVER. na wejściu mamy nieskierowany graf <math>G=(V,E)</math>
| |
| oraz liczbę całkowitą <math>k\leq |V|</math>. Oznaczmy graf wynikowy jako
| |
| <math>G'=(V',E')</math>.
| |
|
| |
| Redukcja przeprowadzona jest techniką gadżetu (w literaturze
| |
| angielskiej uzywa sie również terminu ''widget''). Gadżet to
| |
| fragment struktury wynikowej, o określonych własnościach. W naszym
| |
| przypadku pierwszym krokiem redukcji jest wygenerowanie, dla każdej
| |
| krawędzi <math>(u,v)\in E</math> gadżetu <math>G_{uv}=(V_{uv}, E_{uv})</math> będącego
| |
| grafem przedstawionym na rysunku 5.2.
| |
|
| |
| <center>[[rys_5_2.jpg]]</center>
| |
|
| |
| Jedynie narożne wierzchołki grafu <math>G_{uv}</math> będą połączone z
| |
| wierzchołkami spoza <math>G_{uv}</math>. Stąd wynika, że jeśli <math>G'</math> ma cykl
| |
| Hamiltona, to musi on przechodzić przez <math>G_{uv}</math> tylko na jeden z
| |
| przedstawionych na rysunku 5.3 sposobów. Konstrukcja gadżetu
| |
| uniemożliwia inne usytuowanie cyklu Hamiltona względem <math>G_{uv}</math>.
| |
|
| |
| <center>[[rys_5_3.jpg]]</center>
| |
|
| |
| Drugi krok redukcji to wygenerowanie krawędzi w <math>G'</math> łączących
| |
| gadżety w tak zwane ścieżki. Dla każdego wierzchołka <math>v \in V</math>
| |
| najpierw porządkujemy dowolnie wszystkie jego sąsiednie wierzchołki,
| |
| oznaczmy je przez <math>u_v^1,...,u_v^{d(v)}</math>, gdzie <math>d(v)</math> jest stopniem wierzchołka <math>v</math>. Konstrukcja ścieżki odpowiadającej
| |
| wierzchołkowi <math>v</math>, łączącej wszystkie gadżety odpowiadające
| |
| krawędziom incydentnym z <math>v</math>, dokonuje sie przez dołączenie do <math>G'</math>
| |
| zbioru krawędzi postaci
| |
|
| |
|
| |
| <center><math>E_v=\{([v,u_v^i,6],[v,u_v^{i+1},1]), i=1,\ldots,d(v)-1\}</math></center>
| |
|
| |
|
| |
| Ostatni krok to dodanie wierzchołków-selektorów <math>s_1,\ldots,s_k</math>, i
| |
| połączenie krawędzią każdego selektora z początkiem i końcem ścieżki
| |
| odpowiadającej wierzchołkowi <math>v</math>, dla każdego <math>v</math>.
| |
|
| |
|
| |
| <center><math>E_S=\{(s_i,[v,u_v^1,1]):v\in V, 1\leq i\leq k \}
| |
| \{(s_i,[v,u_v^d(v),6]):v\in V, 1\leq i\leq k</math></center>
| |
|
| |
|
| |
| Kładziemy zatem
| |
|
| |
|
| |
| <center><math>V'=\bigcup_{(uv)\in E}V_{uv}\cup\{s_j, 1\leq j\leq k\}</math></center>
| |
|
| |
|
| |
| <center><math>E'=\bigcup_{(uv)\in E}E_{uv}\cup \bigcup_{v\in V}E_v \cup E_S
| |
| </math></center>
| |
|
| |
|
| |
| <center>[[rys_5_4.jpg]]</center>
| |
|
| |
| Na rys. 5.4 pokazano graf o 4 wierzchołkach i rezultat redukcji.
| |
| Zacieniowane zostały dwa wierzchołki grafu które tworzą pokrycie.
| |
| Pogrubione krawędzie tworza cykl Hamiltona. Zaczynając od selektora
| |
| <math>s_1</math> przechodzimy do początku ścieżki odpowiadającej pierwszemu
| |
| wierzchołkowi z pokrycia, czyli <math>x</math>. Po przejściu gadżetów na tej
| |
| ścieżce wracamy do <math>s_2</math>, a stąd do początku ścieżki odpowiadajacej
| |
| drugiemu węzłowi z pokrycia, <math>y</math>.
| |
|
| |
| Wykażemy, że <math>G'</math> ma cykl Hamiltona wtedy i tylko wtedy gdy G ma
| |
| pokrycie o liczności <math>k</math>.
| |
|
| |
| Załóżmy, że <math>G'</math> ma cykl Hamiltona i prześledźmy jego bieg
| |
| zaczynając od <math>s_1</math> (w dowolnym kierunku). Następny wierzchołek na
| |
| cyklu musi być początkiem (lub końcem - załóżmy to pierwsze) ścieżki
| |
| gadżetów dla pewnego wierzchołka <math>v_1\in V</math>. Dodajemy <math>v_1</math> do generowanego pokrycia. Zgodnie z własnością gadżetu, cykl przebiega
| |
| całą ścieżkę i na końcu przechodzi do innego selektora, załóżmy że
| |
| jest to <math>s_2</math>. Z <math>s_2</math> musi przejść na początek lub koniec innej
| |
| ścieżki, odpowiadającej wierzchołkowi <math>v_2</math>. Dodajemy <math>v_2</math> do
| |
| pokrycia i kontynuujemy. Z ostatniej, <math>k</math>-tej ścieżki, cykl musi
| |
| wrócić do <math>s_1</math>. Ponieważ cykl Hamiltona przeszedł przez wszystkie
| |
| wierzchołki <math>G'</math>, a więc przez wszystkie gadżety <math>G_{uv}</math>, zatem
| |
| wybrane w ten sposób wierzchołki <math>v_1,...,v_k</math> stanowią pokrycie.
| |
|
| |
| Teraz załóżmy, że <math>G</math> ma pokrycie <math>\{v_1,...,v_k\}</math>. Konstruujemy
| |
| cykl Hamiltona w <math>G'</math>. Zaczynamy od selektora <math>s_1</math> i przechodzimy
| |
| na początek ścieżki związanej z <math>v_1</math>, czyli do węzła
| |
| <math>[v_1,u_{v_1}^1,1]</math>. Przechodzimy przez kolejne gadżety aż do końca
| |
| ścieżki. Dla danego gadżetu <math>G_{v_1u_{v_1}^i}</math> musimy podjąć decyzję
| |
| czy przechodzimy przez wszystkie wierzchołki czy tylko przez połowę
| |
| (jedną "ścianę"). Decyzja zależy od tego czy <math>u_{v_1}^i</math> również
| |
| należy do pokrycia. Jeśli nie, to przechodzimy cały gadżet, jeśli
| |
| tak, to drugą "ścianę" pozostawiamy, aby później, gdy trawersowana
| |
| będzie ścieżka dla <math>u_{v_1}^i</math> również można było przejść przez
| |
| <math>G_{v_1u_{v_1}^i}</math>. Z ostatniego węzła na ścieżce przechodzimy do
| |
| selektora <math>s_2</math> i powtarzamy konstrukcję. Z ostatniego węzła na
| |
| <math>k</math>-tej ścieżce wracamy do <math>s_1</math>, zamykając w ten sposób cykl
| |
| Hamiltona.
| |
|
| |
| Ostatnim krokiem dowodu jest stwierdzenie, że konstrukcję grafu <math>G'</math>
| |
| można wykonać posługując się pamięcią roboczą rozmiaru
| |
| logarytmicznego. Wynika to, jak i w poprzednich dowodach, z tego że
| |
| maszynie wystarcza pamięć na licznik położenia w wejściowym grafie
| |
| oraz licznik numeru (nazwy) generowanego wierzchołka i krawędzi
| |
| grafu <math>G'</math>.
| |
|
| |
| }}
| |
|
| |
| Bardzo podobny w sformułowaniu jest problem ścieżki Hamiltona
| |
| (HAMILTONIAN PATH). Na weściu jest graf nieskierowany, na wyjściu
| |
| jest TAK jeśli w grafie istnieje ścieżka przechodząca przez każdy
| |
| wierzchołek dokładnie raz. Oczywiste jest że istnienie cyklu
| |
| Hamiltona implikuje istnienie ścieżki Hamiltona, jednak są to różne
| |
| problemy, i NP-zupełnośc tego drugiwgo wymaga osobnego dowodu. Tym
| |
| niemniej, na przykładzie tych problemów można pokazać pewne techniki
| |
| dowodzenia NP-zupełności w takich przypadkach. Jedną z nich jest
| |
| modyfikacja znanego już dowodu NP-zupełności problemu podobnego,
| |
| drugą zaś redukcja z problemu podobnego.
| |
|
| |
| {{twierdzenie|[HAMILTONIAN PATH]||
| |
| Problem HAMILTONIAN PATH jest NP-zupełny.
| |
| }}
| |
|
| |
| {{cwiczenie||
| |
| Metoda 1: zmodyfikuj konstrukcję grafu <math>G'</math> w dowodzie NP-zupełności
| |
| problemu HAMILTONIAN CYCLE tak aby stanowił dowód NP-zupełności
| |
| problemu HAMILTONIAN PATH.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Należy "wymusić" rozpoczęcie i zakończenie ścieżki dodatkowymi
| |
| selektorami
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:''' <div class="mw-collapsible-content" style="display:none"> Dodajemy selektor <math>s_0</math> i łączymy go krawędzią z <math>s_1</math>.
| |
| następnie dodajemy selektor <math>s_{k+1}</math> i łączymy go z początkami i
| |
| końcami wszystkich ścieżek. na koniec dodajemy <math>s_{k+2}</math> i łączymy
| |
| go z <math>s_{k+1}</math>. Jeśli graf wynikowy posiada ścieżkę Hamiltona, to
| |
| jej końcami muszą być selektory <math>s_0</math> i <math>s_{k+2}</math>. Pozostała część
| |
| rozumowania jest analogiczna.
| |
| </div></div>
| |
| }}
| |
|
| |
| {{cwiczenie||
| |
| Metoda 2: Skonstruuj redukcję z problemu CYKL HAMILTONA.
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Wskazówka:''' <div class="mw-collapsible-content" style="display:none"> Dodaj nowe wierzchołki które będą końcami ścieżki Hamiltona i
| |
| powiąż je odpowiednio z innym wierzchołkami.
| |
| </div></div>
| |
|
| |
| <div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie:''' <div class="mw-collapsible-content" style="display:none"> Nie prowadzi do celu narzucający się pomysł aby dowiązać 2
| |
| nowe wierzchołki do końców dowolnie ustalonej krawędzi. Skuteczna
| |
| jest natomiast modyfikacja tej idei: wybrać dowolny wierzchołek <math>v</math>,
| |
| utworzyć wierzchołek <math>v'</math> o takim samym zbiorze sąsiadów w grafie
| |
| (inaczej: rozszczepić v na dwa identyczne), a nastepnie dołączyć
| |
| nowy wierzchołek <math>u_1</math> do <math>v</math> i jeszcze jeden nowy <math>u_2</math> do <math>v'</math>.
| |
| Łatwo sie przekonać że w nowym grafie istnieje ścieżka Hamiltona
| |
| (koniecznie o końcach <math>u_1, u_2</math>) wtedy i tylko wtedy gdy w
| |
| oryginalnym grafie istnieje cykl Hamiltona.</div></div>
| |
| }}
| |
|
| |
| ==Problemy na zbiorach i liczbach==
| |
|
| |
|
| |
|
| |
| ==Podsumowanie technik dowodów NP-zupełności==
| |
|
| |
| Najprostsze redukcje otrzymujemy metodą zacieśnienia. Przez
| |
| narzucenie dodatkowych zależności w instancjach problemu, o którym
| |
| dowodzimy NP-zupełności, otrzymujemy instancje znanego problemu
| |
| NP-zupełnego. W ten sposób wykazujemy, że nasz problem jest
| |
| uogólnieniem problemu znanego, a więc jest niełatwiejszy. Przykłady
| |
| takich redukcji zastosowaliśmy do problemów: EXACT COVER BY 3SETS,
| |
| SET COVERING, KNAPSACK.
| |
|
| |
| Pozostałe dowody można by zaliczyć do metody gadżetów. Fragmenty
| |
| instancji problemu wejściowego przekształca się we fragmenty
| |
| instancji probelmu wynikowego (gadżety), i wiąże się zależnościami
| |
| (innymi gadżetami), których zachodzenie w problemie wynikowym ma
| |
| mieć ścisłe odzwierciedlenie w spełnieniu wymagań problemu
| |
| źródłowego. Czasem gadżet jest trywialny (np. w redukcji SUBSET SUM
| |
| do PARTITION jest to ta sama waga elementu), kiedy indziej dość
| |
| naturalny i nietrudny (SAT DO 3SAT), czasem bardzo pomysłowy (VERTEX
| |
| COVER do HAMILTONIAN CYCLE, 3SAT do TRIPARTITE MATCHING, 3SAT do
| |
| MAX2SAT).
| |
|
| |
| ==Ćwiczenia końcowe==
| |
|
| |
| ż, że następujący problem izomorfizmu podgrafu jest NP-zupełny:
| |
|
| |
| '''Problem''' SUBGRAPH ISOMORPHISM<br>
| |
| ''Wejście: ''<math>G_1=(V_1, E_1)</math>, <math>G_2=(V_2, E_2)</math> - grafy nieskierowane<br>
| |
| ''Wyjście: ''TAK jeśli <math>G_1</math> ma podgraf izomorficzny z <math>G_2</math>, NIE
| |
| w przeciwnym przypadku.<br>
| |
|
| |
| <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">
| |
| Istnieje redukcja najprostszego typu z jednego z analizowanych
| |
| powyżej problemów.
| |
| </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">
| |
| Jest to proste ugólnienie problemu CLIQUE: szczególnym przypadkiem
| |
| podgrafu o który pytamy w problemie SUBGRAPH ISOMORPHISM jest klika
| |
| o liczności <math>k</math> o która pytamy w problemie CLIQUE.
| |
| </div></div>
| |
|
| |
| tym ćwiczeniu pytamy o trudność obliczeniową
| |
| problemu pochodzącego z teorii szergowania. Wykaż, że NP-zupełny
| |
| jest następujący problem:
| |
|
| |
| '''Problem''' SEQUENCING WITHIN INTERVALS<br>
| |
| ''Wejście: ''Zbiór zadań <math>T</math>, dla każdego zadania <math>t</math> trzy liczby
| |
| całkowite: długość zadania <math>l(t)> 0</math>, moment pojawienia się
| |
| <math>r(t)\geq 0</math>,oraz ograniczenie czasowe <math>d(t)>0</math><br>
| |
| ''Wyjście: ''TAK, jeśli wszystkie zadania można wykonać na jednym
| |
| procesorze, bez przerywania, spełniając ograniczenia czasowe, NIE w
| |
| przeciwnym przypadku. Formalnie, pytamy o funkcję alokacji <math>A</math>
| |
| przydzielająca każdemu zadaniu <math>t</math> czas rozpoczęcia wykonywania
| |
| <math>A(t)</math> taki, że <math>[A(t), A(t)+l(t)] \subseteq [r(t),d(t)]</math> oraz
| |
| <math>[A(t), A(t)+l(t)) \cap [A(t'), A(t')+l(t')) = \emptyset</math>, dla
| |
| każdego zadania <math>t' \neq t</math>.<br>
| |
|
| |
| <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">
| |
| Spróbuj, układając na prostej (osi liczbowej) odpowiednio
| |
| zdefiniowany ciąg odcinków (zadań), wymusić istnienie podzbioru o
| |
| zadanej sumie.
| |
| </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">
| |
| Redukcja z problemu SUBSET SUM za pomocą bardzo prostych gadżetów.
| |
| Niech <math>s_1, \ldots,s_n</math> oraz <math>B</math> będą odpowiednio wagami elementów
| |
| oraz żądana sumą podzbioru elementów. Niech <math>D=\sum_{i=1}^n s_i</math>.
| |
| Konstruujemy <math>n+1</math> zadań, przy czym dla <math>i=1,\ldots,n</math> zadanie <math>t_i</math>
| |
| ma długość <math>l_i=s_i</math>, czas gotowości <math>r_i=0</math> oraz granicę <math>d_i=D+1</math>.
| |
| Zadanie <math>t_{n+})</math> jest "wymuszaczem podziału", o parametrach
| |
| <math>l_i=1</math>, <math>r_i=B</math>, <math>d_i=B+1</math>.
| |
|
| |
| Zadania <math>s_1, \ldots,s_n</math> mają pozorną swobodę wykonywania sie w
| |
| dowolnym miejscu osi czasu, zauważmy jednak że każde ulokowanie
| |
| wszystkich zadań nie zostawia żadnej luki na osi. Dla wymuszacza
| |
| jest tylko jedna możliwa wartość alokacji, <math>B</math>. Takie położenie
| |
| dzieli cały przedział, w którym moga byc wykonywane zadania, na dwa
| |
| podprzedziały, rozdzielone wymuszaczem. Jeden z tych przedziałów ma
| |
| długość <math>B</math>, zatem ulokowanie zadań na osi, zgodne z warunkami
| |
| zadania, jest możliwe wtedy i tylko wtedy gdy istnieje podzbiór
| |
| zbioru elementów w instancji problemu SUBSET SUM, ktych wagi dają w
| |
| sumie <math>B</math>.
| |
| </div></div>
| |
|
| |
| ====section====
| |
|
| |
| Problem cięcia w grafie zdefiniowany jest następująco:
| |
|
| |
| '''Problem''' FEEDBACK VERTEX SET<br>
| |
| ''Wejście: ''Graf skierowany <math>G=(V, E)</math>, liczba całkowita <math>k, 0<k\geq |V|</math>.<br>
| |
| ''Wyjście: ''TAK jeśli istnieje w <math>G</math> podzbiór <math>k</math>-wierzchołkowy,
| |
| taki że graf pozostały po usunięciu tego podzbioru jest
| |
| acykliczny.<br>
| |
| Udowodnij, że FEEDBACK VERTEX SET jest NP-zupełny.
| |
|
| |
| <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">
| |
| Jak zwykle, najtrudniej dobrać problem źródłowy dla redukcji.
| |
| Proponujemy pokrycie wierzchołkowe. Jak powinien wyglądać wynik
| |
| redukcji -- graf skierowany -- aby rozcinanie wszsytkich cykli przez
| |
| usuwanie wierzchołków znaczyło to samo co definiowanie pokrycia w
| |
| grafie źródłowym?
| |
| </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">
| |
| Na wejściu mamy graf nieskierowany <math>G=(V,E)</math> i liczbę <math>k</math>.
| |
| Zamieniamy ten graf na graf skierowany <math>G'</math>, z tym samym zbiorem
| |
| wierzchołków, zastępując każdą krawędź nieskierowaną <math>(u,v)</math> przez
| |
| dwie krawędzie skierowane: <math>(u,v)</math> oraz <math>(v,u)</math>. Liczba <math>k</math> jest
| |
| taka sama dla obu instancji.
| |
|
| |
| Nietrudno zauważyć, że każde pokrycie wierzchołkowe w <math>G</math> jest
| |
| zbiorem rozcinającym wszystkie cykle w <math>G'</math> i na odwrót.
| |
| </div></div>
| |
|
| |
| ====section====
| |
|
| |
| Kolorowanie (wierzchołkowe) grafu jest klasycznym problemem
| |
| optymalizacyjnym w teorii grafów. Przypomnijmy, że chodzi o
| |
| przypisanie wierzchołkom grafu nieskierowanego kolorów tak, aby
| |
| końce każdej krawędzi miały różne kolory, a liczba kolorów była
| |
| możliwie najmniejsza.
| |
|
| |
| Okazuje sie że nawet jeśli ustalimy żądaną liczbe kolorów na 3, to
| |
| problem jest NP-zupełny. Dowód tego faktu nie jest natychmiastowy.
| |
|
| |
| '''Problem''' 3COLORING<br>
| |
| ''Wejście: ''Graf nieskierowany <math>G=(V,E)</math>. <br>
| |
| ''Wyjście: ''TAK, jeśli istnieje funkcja <math>c : V \rightarrow
| |
| \{0,1,2\}</math> taka, że dla każdej krawędzi <math>(u,v)\in E</math>, <math>c(u)\neq
| |
| c(v)</math>.<br>
| |
| Za pomocą redukcji z problemu 3SAT udowodnij, że problem
| |
| trójkolorowania jest NP-zupełny.
| |
|
| |
| <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">
| |
| Można użyć gadżetu przedstawionego na rysunku 5.6.
| |
| {1cm}
| |
|
| |
| [width<nowiki>=</nowiki>12cm]{rys_5_6.jpg}<br>
| |
|
| |
| {1cm}
| |
| '''UWAGA DLA REDAKCJI: RYSUNEK POJAWIA
| |
| SIĘ JAKO CZĘŚĆ WSKAZÓWKI'''
| |
| </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">
| |
| Gadżet ma następujące własności:
| |
|
| |
| * jeśli wierzchołkom <math>u,v,z</math> przypisano kolory tak, że co najmniej
| |
| jeden z nich ma kolor 1, to istnieje uzupełnienie trójkolorowania
| |
| pozostałych wierzchołków takie, że <math>c(z)=1</math>
| |
|
| |
| * jeśli w danym trójkolorowaniu <math>c(u)=c(v)=c(z)=0</math>, to
| |
| również <math>c(z)=0</math>.
| |
|
| |
| Redukcję przeprowadzamy następująco:
| |
|
| |
| # generujemy wierzchołki <math>s,t,z</math> i trójkat oparty na nich
| |
|
| |
| # Dla każdej zmiennej <math>x</math> występującej w instancji 3SAT definiujemy
| |
| wierzchołki <math>x, \neg x</math> oraz trójkąt oparty na <math>x,\neg x</math> oraz <math>t</math>
| |
|
| |
| # dla każdej klauzuli <math>C_j=(u\vee v\vee w)</math> definiujemy kopię gadżetu,
| |
| przy czym wierzchołki <math>u,v,w</math> to już wygenerowane w punkcie 2
| |
| wierzchołki literałów o tych samych nazwach, wierzchołek <math>z</math> został
| |
| wygenerowany w kroku 1, natomiast pozostałe wierzchołki są nowe,
| |
| unikalne dla każdej klauzuli
| |
|
| |
| {1cm}
| |
|
| |
| [width<nowiki>=</nowiki>12cm]{rys_5_7.jpg}<br>
| |
|
| |
| {1cm}
| |
|
| |
| Wykazemy, że formuła źródłowa ma spełniające wartościowanie wtedy i
| |
| tylko wtedy gdy wygenerowany graf można pokolorować trzema kolorami.
| |
|
| |
| Jeśli istnieje wartościowanie spełniające formułę, to
| |
|
| |
| * kładziemy <math>c(s)=0</math>, <math>c(z)=1</math> <math>c(t)=2</math>
| |
|
| |
| * kolorujemy każdy z wierzchołków <math>x_i, \neg x_i</math> jego wartością
| |
| logiczną, 0 lub 1
| |
|
| |
| * uzupełniamy kolory 0, 1, i 2 w gadżetach -- można to zrobić gdyż
| |
| zadane wartościowanie spełnia formułę, a więc na wejściu do każdego
| |
| gadżetu jest co najmniej jeden wierzchołek koloru 1
| |
|
| |
| Jeśli zadane jest trójkolorowanie grafu, to obliczamy wartościowanie
| |
| spełniające formułę następująco:
| |
|
| |
| * kolory wierzchołków <math>s,t,z</math> są różne, więc umawiamy się, że <math>c(s)=0,
| |
| c(t)=2, c(z)=1</math>
| |
|
| |
| * dla każdej zmiennej <math>x_i</math> kładziemy wartość tej zmiennej równą
| |
| <math>c(x_i)</math>. Ponieważ <math>c(t)=2</math> więc wartość ta wynosi 0 lub 1.
| |
|
| |
| Ponieważ <math>c(z)=1</math>, więc dla każdego gadżetu co najmniej jeden z jego
| |
| trzech wejściowych wierzchołków ma kolor 1, a zatem w każdej
| |
| klauzuli mamy co najmniej jedną jedynkę.
| |
| </div></div>
| |
