|
|
| Linia 2: |
Linia 2: |
| <math>M</math> <math>M'</math> <math>M' </math> | | <math>M</math> <math>M'</math> <math>M' </math> |
| <math>a^{\sum_{i=1}^{10}i}</math> | | <math>a^{\sum_{i=1}^{10}i}</math> |
|
| |
| {{cwiczenie|[Uzupelnij]||
| |
| abc
| |
| }}
| |
|
| |
| <hr>
| |
|
| |
| {article}
| |
|
| |
| {}{0.5cm} {}{0.8cm} {}{ -0.4cm} {}{ -0.4cm} {}{1mm}
| |
|
| |
| {theorem}{Twierdzenie}[section]
| |
| {lemma}[theorem]{Lemat}
| |
| {definition}[theorem]{Definicja}
| |
| {example}{Przykład}[section]
| |
| {excercise}{Ćwiczenie}[section]
| |
| {remark}{Uwaga}[section]
| |
|
| |
| {proof}{ ''Dowód: ''}{ <math>\square</math>}
| |
| {hint}{ ''Wskazówka: ''}{}
| |
| {solution}{ ''Rozwiązanie: ''}{}
| |
|
| |
| Złożoność obliczeniowa
| |
|
| |
| Moduł 5
| |
|
| |
| Problemy NP-zupełne
| |
|
| |
| ==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|[Uzupelnij]||
| |
| Problem 3SAT jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| 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 \ldots
| |
| \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,\ldots,x_k</math>, to da się tak dobrać
| |
| wartości dla zmiennych <math>y_2,\ldots,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,\ldots,x_k,y_2,\ldots,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|[Uzupelnij]||
| |
| 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|[Uzupelnij]||
| |
| 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|[Uzupelnij]||
| |
| Problem MAX2SAT jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| Konstruujemy redukcję z problemu 3SAT. Na wejściu mamy formułę
| |
| <math>\phi=C_1 \vee \ldots\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<br>
| |
| ''Wejście:'' Graf nieskierowany <math>G=(V,E)</math>, liczba całkowita <math>k\leq
| |
| |V|</math><br>
| |
| ''Wyjście'': TAK jeśli G ma pokrycie wierzchołkowe o liczności k,
| |
| NIE w przeciwnym przypadku.
| |
|
| |
| {{twierdzenie|[Uzupelnij]||
| |
| Problem NODE COVER jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| Dla podanego podzbioru zbioru wierzchołków bardzo łatwo sprawdzić
| |
| czy stanowi on pokrycie, zatem <math>{\textsc NODE COVER}\in NP</math>.
| |
|
| |
| Redukujemy problem 3SAT do NODE COVER. Na wejściu mamy formułę
| |
| <math>\phi=C_1 \wedge\ldots\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>.
| |
|
| |
| {1cm}
| |
|
| |
| [width<nowiki>=</nowiki>12cm]{rys_5_1.jpg}<br>
| |
| Redukcja 3SAT do NODE COVER
| |
|
| |
| {1cm}
| |
|
| |
| 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>\log n</math>, co kończy dowód.
| |
| }}
| |
|
| |
| ===Klika, zbiór niezależny===
| |
|
| |
| Przypomnijmy definicje obu problemów:
| |
|
| |
| '''Problem''' INDEPENDENT SET<br>
| |
| ''Wejście:'' Graf nieskierowany <math>G=(V,E)</math>, liczba całkowita <math>k\leq
| |
| |V|</math><br>
| |
| ''Wyjście'': TAK jeśli <math>G</math> ma zbiór niezależny (indukowany podgraf
| |
| bez krawędzi) o <math>k</math> wierzchołkach, NIE w przeciwnym przypadku.
| |
|
| |
| '''Problem''' CLIQUE<br>
| |
| ''Wejście:'' Graf nieskierowany <math>G=(V,E)</math>, liczba całkowita <math>k\leq
| |
| |V|</math><br>
| |
| ''Wyjście'': TAK jeśli <math>G</math> ma podgraf pełny (klikę) o <math>k</math>
| |
| wierzchołkach, NIE w przeciwnym przypadku.
| |
|
| |
| {{cwiczenie||
| |
| Wykaż, że problem INDEPENDENT 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"> Jeśli <math>V'</math> jest pokryciem wierzchołkowym, to jaką własność
| |
| ma zbiór <math>V-V'</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"> Dopełnienie pokrycia jest oczywiście zbiorem
| |
| niezależnym. Zatem redukcja z problemu NODE COVER, mając na wejściu
| |
| graf <math>G=(V,E)</math> i liczbę <math>k</math> generuje instancję <math>G'=(V',E'),k'</math>
| |
| problemu INDEPENDENT SET, kładąc <math>G'=G</math>, <math>k'=|V|-k</math>.
| |
| </div></div>
| |
|
| |
| {{cwiczenie||
| |
| Wykaż, że problem INDEPENDENT SET jest NP-zupełny, wykorzystując
| |
| pokazaną wyżej redukcję z 3SAT do NODE COVER, zmieniając tylko
| |
| rozumowanie tak, aby odnosiło sie do problemu INDEPENDENT SET.
| |
| }}
| |
|
| |
| {{cwiczenie||
| |
| Wykaż, że problem CLIQUE 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"> Rozważ dopełnienie grafu.
| |
| </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 INDEPENDENT SET. Graf wynikowy
| |
| jest dopełnieniem grafu źródłowego, a parametr <math>k</math> ma tę sama wartość.
| |
| </div></div>
| |
|
| |
| ===Cykl i ścieżka Hamiltona===
| |
|
| |
| '''Problem''' HAMILTONIAN CYCLE<br>
| |
| ''Wejście:'' Graf nieskierowany <math>G=(V,E)</math><br>
| |
| ''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|[Uzupelnij]||
| |
| CYKL HAMILTONA jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| 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.
| |
|
| |
| {1cm}
| |
|
| |
| [width<nowiki>=</nowiki>12cm]{rys_5_2.jpg}<br>
| |
|
| |
| {1cm}
| |
|
| |
| 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>.
| |
|
| |
| {1cm}
| |
|
| |
| [width<nowiki>=</nowiki>12cm]{rys_5_3.jpg}<br>
| |
|
| |
| {1cm}
| |
|
| |
| 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,\ldots,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\} \cup
| |
| \{(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>
| |
|
| |
| {1cm}
| |
|
| |
| [width<nowiki>=</nowiki>12cm]{rys_5_4.jpg}<br>
| |
|
| |
| {1cm}
| |
|
| |
| 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,\ldots,v_k</math> stanowią pokrycie.
| |
|
| |
| Teraz załóżmy, że <math>G</math> ma pokrycie <math>\{v_1,\ldots,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|[Uzupelnij]||
| |
| 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"><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">
| |
| Należy "wymusić" rozpoczęcie i zakończenie ścieżki dodatkowymi
| |
| selektorami
| |
| </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">
| |
| 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"><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">
| |
| 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"><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">
| |
| 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==
| |
|
| |
| ===Trójdzielne skojarzenie i pokrycie zbiorami===
| |
|
| |
| Uogólnieniem klasycznego problemu skojarzenia w grafie dwudzielnym
| |
| jest następujący problem:
| |
|
| |
| '''Problem '''TRIPARTITE MATCHING<br>
| |
| ''Wejście: ''parami rozłączne równoliczne zbiory <math>W,X,Y</math> o mocy
| |
| <math>p>0</math> oraz relacja <math>R\subseteq W\times X\times Y</math><br>
| |
| ''Wyjście: ''TAK, jeśli istnieje skojarzenie w <math>R</math>, czyli podzbiór
| |
| <math>R' \subseteq R</math> taki, że dla dowolnych trójek
| |
| <math>(w,x,y),(w',x',y')\in R</math> zachodzi
| |
| <math>w\neq w'</math>, <math>x\neq x'</math> oraz <math>y\neq y'</math>. NIE w przeciwnym przypadku.<br>
| |
|
| |
| Problem skojarzenia dwudzielnego jest obliczeniowo łatwy.
| |
| Uogólnienie do trzech wymiarów utrudnia problem radykalnie.
| |
|
| |
| {{twierdzenie|[Uzupelnij]||
| |
| Problem TRIPARTITE MATCHING jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| Ponownie mamy do czynienia z dość skomplikowaną konstrukcją
| |
| posługującą się gadżetami, redukującą problem 3SAT do naszego
| |
| problemu.
| |
|
| |
| Na wejściu mamy zbiór klauzul <math>C=\{C_1,\ldots,C_m\}</math> nad zmiennymi
| |
| <math>U=\{u_1,\ldots,u_n\}</math>. Najpierw dla każdej zmiennej <math>u\in U</math>
| |
| konstruujemy gadżet <math>T_u</math>, który będzie odpowiadał za wybór
| |
| wartościowania tej zmiennej. Składa się on z dwóch zbiorów trójek:
| |
|
| |
| <center><math>
| |
| T_u^t=\{(w_{2j}^u,x_j^u,y_j^u), 1\leq j\leq m\}</math></center>
| |
|
| |
| <center><math>
| |
| T_u^f=\{(w_{2j+1}^u,x_{j+1}^u,y_j^u), 1\leq j<m\}\cup\{(w_1^u,x_1^u,y_m^u)\}</math></center>
| |
|
| |
| Przykładowy gadżet dla zmiennej <math>u</math>, w przypadku gdy liczba klauzul
| |
| wynosi <math>m=4</math> pokazano na rysunku 5.5. Grubą linią zaznaczono trójki
| |
| ze zbioru
| |
|
| |
| {1cm}
| |
|
| |
| [width<nowiki>=</nowiki>12cm]{rys_5_5.jpg}<br>
| |
|
| |
| {1cm}
| |
|
| |
| Dla każdego gadżetu pierwsze elementy trójek, <math>w_1^u,\ldots,w_m^u</math>,
| |
| występują jeszcze w innych trójkach, które za chwilę zdefiniujemy.
| |
| Pozostałe elementy występuja tylko w danym gadżecie. Zatem, jeśli
| |
| wybrano skojarzenie, to dla ustalonego gadżetu to skojarzenie
| |
| zawiera albo cały zbiór <math>T_u^f</math> i żadnej trójki z <math>T_u^t</math>, albo na
| |
| odwrót. W toku dalszego rozumowania, wybór do skojarzenia zbioru
| |
| <math>T_u^f</math> będzie oznaczał wartościowanie zmiennej <math>u</math> na ''false'' i
| |
| pozostawi niepokryte elementy <math>w</math> o indeksach parzystych. Wybór
| |
| przeciwny ustali wartościowanie <math>u</math> na ''true'' i pozostawi
| |
| niepokryte elementy <math>w</math> o indeksach nieparzystych. Sytuacja taka
| |
| została przedstawiona na rysunku 5.5, pogrubioną linią zaznaczono
| |
| wybór trójek <math>T_u^t</math>.
| |
|
| |
| Trójki które zdefiniujemy teraz mogą być nazwane "składową
| |
| testowania". Skojarzą one niepokryte elementy z gadżetów z
| |
| odpowiednimi wystąpieniami literałów w klauzulach. Dla każdej
| |
| klauzuli <math>C_j=(p_j\vee q_j\vee r_j)</math> składowa testowania <math>S_j</math>
| |
| zawiera 3 trójki <math>s_j^1,s_j^2,s_j^3</math> odpowiadajace kolejnym
| |
| literałom <math>p,q,r</math>, zdefiniowane następująco: Jeśli <math>p=u_i</math> to
| |
| <math>s_j^1=(w_{2j-1}^u,a_j, b_j)</math>. Jeśli <math>p=\neg u_i</math> to
| |
| <math>s_j^1=(w_{2j}^u,a_j,b_j)</math>. Analogicznie dla literałów <math>q, r</math>.
| |
|
| |
| Elementy <math>a_j, b_j</math> występują tylko w trzech trójkach zbioru <math>S_j</math>,
| |
| zatem skojarzenie wybiera dokładnie jedną z tych trójek. Aby móc
| |
| daną trójkę wybrać, element na pierwszej współrzędnej w tej trójce
| |
| musi być niepokryty trójkami z odpowiedniego gadżetu. Ale to oznacza
| |
| że wartość danego literału jest ''true'', czyli klauzula <math>C_j</math>
| |
| jest spełniona. Innymi słowy, możliwość pokrycia elementów <math>a_j,
| |
| b_j</math> jest równoważna temu, że istnieje w klauzuli <math>C_j</math> literał o
| |
| wartości logicznej ''true''.
| |
|
| |
| Skojarzenie wybrane dla gadżetów ma liczność <math>nm</math>, składowa
| |
| testowania daje kolejnych <math>m</math> trójek w skojarzeniu, zatem ze
| |
| wszystkich <math>2nm</math> elementów na pierwszej współrzędnej (elementy <math>u</math>)
| |
| <math>(n-1)m</math> pozostaje nieskojarzonych. Zatem w konstrukcji potrzebna
| |
| jest jeszcze trzecia "składowa odśmiecania" zdefiniowana
| |
| nastepująco:
| |
|
| |
| <center><math>
| |
| G=\{(w_i^u,g_k,h_k):u\in U, 1\leq i\leq 2m, 1\leq k\leq (n-1)m\}</math></center>
| |
|
| |
| Pozwala ona skojarzyć elementy <math>u</math> pozostałe po wyborze
| |
| wartościowania i testu spełnialności.
| |
|
| |
| Na podstawie opisanej konstrukcji i komentarzy jej towarzyszących
| |
| możemy juz łatwo stwierdzić, że formuła wejściowa posiada
| |
| wartościowanie spełniające wtedy i tylko wtedy gdy utworzony w
| |
| wyniku redukcji zbiór trójek ma skojarzenie.
| |
| }}
| |
|
| |
| Rozważmy jeszcze trzy podobne problemy na zbiorach. Ich NP-zupełność
| |
| stanie sie oczywista gdy zauważymy że stanowią one kolejne
| |
| uogólnienia problemu trójdzielnego skojarzenia.
| |
|
| |
| '''Problem '''EXACT COVER BY 3-SETS (pokrycie trójelementowymi podzbiorami)<br>
| |
| ''Wejście: ''Rodzina <math>\cal F</math> trójelementowych podzbiorów zbioru
| |
| <math>X</math>
| |
| takiego że <math>|X|=3k</math> dla pewnej calkowitej <math>k</math><br>
| |
| ''Wyjście: ''TAK jesli istnieje podrodzina <math>\cal F' \subseteq \cal
| |
| F</math> taka, że każdy element zbioru <math>X</math> należy do dokładnie jednego zbioru rodziny <math>\cal F"</math>,
| |
| NIE w przeciwnym przypadku<br>
| |
|
| |
| {{cwiczenie||
| |
| Wykaż że EXACT COVER BY 3-SETS 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">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">
| |
| Zauważ, że jeśli ograniczymy sie do instancji w których X jest
| |
| podzielone na trzy rozłączne równoliczne zbiory, a wszystkie
| |
| podzbiory w rodzinie <math>F</math> zawieraja po jednym elemencie z każdego z
| |
| tych trzech podzbiorów, to otrzymujemy problem TRIPARTITE MATCHING
| |
| (formalnie są to izomorficzne struktury). Zatem EXACT COVER BY
| |
| 3-SETS jest uogólnieniem TRIPARTITE MATCHING, a ponieważ, co
| |
| oczywiste, jest w NP, więc jest NP-zupełny.
| |
| </div></div>
| |
|
| |
| '''Problem''' SET COVERING (pokrycie zbiorami)<br>
| |
| ''Wejście: ''Rodzina <math>F=\{S_1,\ldots,S_n\}</math> podzbiorów zbioru
| |
| <math>|X|</math>,
| |
| liczba całkowita <math>k\leq n</math><br>
| |
| ''Wyjście: ''TAK, jeśli istnieje k-elementowa podrodzina rodziny
| |
| <math>F</math>,
| |
| która pokrywa cały zbiór <math>|X|</math>, w przeciwnym przypadku NIE.<br>
| |
|
| |
| {{cwiczenie||
| |
| Wykaż NP-zupełność problemu SET COVERING.
| |
| }}
| |
|
| |
| <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">
| |
| Ponownie przez ograniczenie do podproblemu: jeśli założymy że
| |
| <math>|X|=3k</math> a wszystkie zbiory rodziny <math>F</math> są 3-elementowe, to
| |
| otrzymujemy problem EXACT COVER BY 3-SETS.
| |
| </div></div>
| |
|
| |
| ===Suma podzbioru i inne problemy liczbowe===
| |
|
| |
| Teraz zajmiemy się kilkoma problemami związanymi z liczbami.
| |
| Najwięcej trudu będzie kosztować udowodnienie NP-zupełności
| |
| pierwszego z nich -- następne pójdą już łatwiej. Ta pierwsza
| |
| trudność zasadza się na tym, że jak do tej pory dowodziliśmy
| |
| NP-zupełność tylko dla problemów, w których tak naprawdę nie ma
| |
| liczb, jako elementów struktury kombinatorycznej. Oczywiście, każde
| |
| słowo wejściowe może byc traktowane jako liczba, kod maszyny Turinga
| |
| tez jest liczbą. Tutaj jednak chodzi o naturalne sformułowanie
| |
| problemu, w odniesieniu do obiektów abstrakcyjnych takich jak
| |
| liczby, funkcje, relacje, grafy itd. Problematyka trudności
| |
| obliczeniowej problemów z liczbami jest rozwinięta w następnej
| |
| lekcji.
| |
|
| |
| '''Problem '''SUBSET SUM (suma podzbioru)<br>
| |
| ''Wejście: ''Skończony zbiór <math>A</math> elementów, dla każdego elementu
| |
| <math>a\in A</math> waga <math>s(a)\in Z^+</math> oraz liczba <math>B\in Z^+</math>. <br>
| |
| ''Wyjście: ''TAK jeśli istnieje podzbiór <math>A'\subseteq A</math> taki że
| |
| <math>\sum_{a\in A'}s(a) = B</math>, NIE w przeciwnym przypadku. <br>
| |
|
| |
| {{twierdzenie|[Uzupelnij]||
| |
| Problem SUBSET SUM jest NP-zupełny.
| |
| }}
| |
|
| |
| {{dowod|[Uzupelnij]||
| |
| Skonstruujemy redukcję z problemu EXACT COVER BY 3 SETS. Na wejściu
| |
| mamy zatem zbiór <math>X</math> o liczności <math>3m</math> i rodzinę
| |
| <math>F=\{U_1,\ldots,U_n\} </math> jego podzbiorów. Naszym zadaniem jest
| |
| skonstruować zbiór <math>Y</math> elementów z pewnymi wagami oraz liczbę B
| |
| taką, że istnienie podzbioru w <math>Y</math> o sumie wag elementów równej <math>B</math>
| |
| "wymusza" istnienie pokrycia zbioru <math>X</math> wybranymi rozłącznymi
| |
| podzbiorami z rodziny <math>F</math>.
| |
|
| |
| Niech <math>p=\lceil\log_2(n+1)\rceil</math>. Najpierw ustalamy porządek
| |
| elementów w zbiorze <math>|X|</math> i zapisujemy każdy zbiór <math>U_j</math> jako wektor
| |
| <math>3m</math>-bitowy (czyli jest to struktura danych -- wektor bitowy --
| |
| reprezentująca podzbiór danego zbioru). W każdym wektorze są
| |
| oczywiście 3 bity równe 1 a pozostałe są zerowe. Następnie przed
| |
| każdym bitem wstawiamy dodatkowo <math>p-1</math> bitów zerowych i traktujemy
| |
| ten wektor kjako liczbe zapisaną binarnie. Powstaje w ten sposób <math>n</math>
| |
| liczb <math>3mp</math>-bitowych -- są to wagi elementów zbioru Y. Liczba <math>B</math>
| |
| jest również takiej długości, powstaje przez wypisanie <math>3m</math> jedynek
| |
| a następnie wstawienie przed każdą jedynką <math>p-1</math> zer.
| |
|
| |
| Jeśli istnieje podrodzina <math>F'\subseteq F</math> stanowiąca rozłączne
| |
| pokrycie zbioru <math>X</math>, to wektory bitowe poszczególnych trójek z <math>F'</math>
| |
| arytmetycznie sumują sie do <math>B</math>, a na żadnej pozycji nie występuje
| |
| przeniesienie. Zatem z istnienia pokrycia wynika istnienie podzbioru
| |
| dającego w sumie wagę <math>B</math>.
| |
|
| |
| Bloki zer dodane przed każdym bitem reprezentacji wektorowej
| |
| podzbioru gwarantują, że sumując dowolny podzbiór wygenerowanych
| |
| liczb nie napotkamy na przeniesienie poza taki blok zer. A zatem,
| |
| jeśli istnieje podzbiór liczb dający w sumie <math>B</math>, to wszystkie te
| |
| liczby w swoich rozwinięciach binarnych zawierają w sumie tyle
| |
| jedynek ile jest ich w <math>B</math>, na różnych pozycjach. A więc
| |
| odpowiadajace tym liczbom podzbiory pokrywają cały zbiór <math>X</math>.
| |
|
| |
| Zatem opisane przekształcenie jest redukcją. Jak w poprzednich
| |
| dowodach, potrzebna jest pamięć robocza jedynie na stałą liczbę
| |
| liczników. A więc jest to redukcja logarytmiczna.
| |
| }}
| |
|
| |
| W tej części lekcji wykażemy NP-zupełność dwóch podobnych
| |
| problemów liczbowych.
| |
|
| |
| '''Problem '''PARTITION (podział)<br>
| |
| ''Wejście: ''Skończony zbiór <math>A</math> elementów oraz dodatnia całkowita
| |
| waga <math>s(a)</math> każdego elementu<br>
| |
| ''Wyjście: ''TAK jeśli istnieje podzbiór <math>A'\subseteq A</math> taki że
| |
| <math>\sum_{a\in A'}s(a) = \sum_{a\in A-A'}s(a)</math>, NIE w przeciwnym
| |
| przypadku.
| |
|
| |
| {{cwiczenie||
| |
| Wykaż NP-zupełność problemu podziału.
| |
| }}
| |
|
| |
| <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">
| |
| Skorzystaj z SUBSET SUM. Wystarczy dodać dwa elementy o odpowiednio
| |
| dobranej dużej wadze.
| |
| </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">
| |
| Niech <math>S=\sum_{a\in A}s(a)</math>. Dodajemy do zbioru dwa elementy <math>b_1</math> i
| |
| <math>b_2</math>, <math>s(b_1)=2S-B, s(b_2)=S+B</math>. Łatwo sprawdzić, że:
| |
|
| |
| * Jeśli w zbiorze <math>A</math> istnieje podzbiór <math>A'</math> o sumie równej <math>B</math>,
| |
| to podzbiór ten z dołączonym elementem <math>b_1</math> daje sumę równą <math>2S</math>,
| |
| tyle co pozostałe elementy uzupełnione o <math>b_2</math>.
| |
|
| |
| * jeśli w zbiorze <math>A\cup \{b_1,b_2\}</math> istnieje podział na 2
| |
| podzbiory o jednakowych wagach, to elementy <math>b_1</math> i <math>b_2</math> sa w
| |
| różnych podzbiorach, bo ich wagi sumują się do <math>3S</math>. W tym
| |
| podzbiorze do którego należy <math>b_1</math> suma wag pozostałych elementów
| |
| wynosi <math>B</math>.
| |
|
| |
| </div></div>
| |
|
| |
| '''Problem '''KNAPSACK (plecak)<br>
| |
| ''Wejście: ''Skończony zbiór <math>A</math> elementów, rozmiar <math>s(a)\in Z^+</math>
| |
| i wartość <math>v(a)\in Z^+</math> dla każdego elementu, ograniczenie
| |
| pojemności <math>B\in Z^+</math> oraz żądana wartość <math>K\in Z^+</math><br>
| |
| ''Wyjście: ''TAK jeśli istnieje podzbiór <math>A'\subseteq A</math> taki że
| |
| <math>\sum_{a\in A'}s(a) \leq B</math> oraz <math>\sum_{a\in A}v(a)\geq K</math>, NIE w
| |
| przeciwnym przypadku.
| |
|
| |
| {{cwiczenie||
| |
| Pokaż że KNAPSACK 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">
| |
| Wykorzystaj SUBSET SUM lub PARTITION.
| |
| </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">
| |
| Jeśli założymy, że rozmiary elementów są równe ich wartościom, a
| |
| pojemnośc plecaka jest równa żądanej wartości, to otrzymamy problem
| |
| SUBSET SUM.
| |
| </div></div>
| |
|
| |
| ==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==
| |
|
| |
| {{cwiczenie|| Wykaż, ż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>
| |
|
| |
| {{cwiczenie|| W 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>
| |
|
| |
| {{cwiczenie||
| |
| 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>
| |
|
| |
| {{cwiczenie||
| |
| 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>
| |
