Złożoność obliczeniowa/Wykałd 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 $Q$ z klasy NP jest NP-zupełny, zgodnie z własnościami redukcji logarytmicznej (przechodniość) wystarcza pokazać, dla dowolnego problemu $Q^{\prime }\in NPC$, że $Q^{\prime }$ redukuje się do $Q$. Innymi słowy, proces dowodzenia że dany problem $Q$ jest w NPC składa sie z nastepujących kroków:

• dowieść że $Q$ należy do NP

• wybrać znany problem NP-zupełny $Q^{\prime }$ i skonstruować redukcję z $Q^{\prime }$ do $Q$.

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.

Dowód

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 $\varphi =C_1\wedge \dots \wedge C_m$ nad zmiennymi $x_1,\dots ,x_n$. Każdą z klauzul $C_j$ przekształcamy osobno. Bez straty ogólności załóżmy, że $C_j=x_1\vee \dots \vee x_k$, gdzie $x_i,i=1,\dots ,k$ są parami różne. Jeśli $k\le 3$ to kładziemy $D_j=C_j$.

Niech $k>3$. Dodajemy $k-3$ nowych zmiennych $y_2,\dots ,y_{k-2}$, i zastepujemy $C_j$ przez

$D_j=(x_1\vee x_2\vee y_2)\wedge (\mathrm{\neg }{y}_2\vee x_3\vee y_3)\wedge (\mathrm{\neg }{y}_3\vee x_4\vee y_4)\wedge ...\wedge (\mathrm{\neg }{y}_{k-2}\vee x_{k-1}\vee x_k)$

Nietrudno spostrzec, że jeśli $C_j$ jest spełniona przez pewne wartościowanie zmiennych $x_1,...,x_k$, to da się tak dobrać wartości dla zmiennych $y_2,...,y_{k-2}$, aby spełnione były wszystkie klauzule w $D_j$. Na odwrót, jeśli $D_j$ jest spełniona dla pewnego wartościowania zmiennych $x_1,...,x_k,y_2,...,y_{k-2}$, to łatwo wydedukować, że $x_i=1$ dla pewnego $1\le i\le k$. Mianowicie, jeśli $x_1=x_2=0$, to z pierwszej klauzuli w $D_j$ wynika że $y_2=1$. Ale wtedy z drugiej klauzuli mamy $x_3=1$ lub $y_3=1$. 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 $C_j$ 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 $k=2$. Wprowadzamy nową zmienną $y$ i kładziemy $D_j=(x_1\vee x_2\vee y)\wedge (x_1\vee x_2\vee \mathrm{\neg }y)$. Jeśli istnieje wartościowanie spełniające formułę $\varphi$, to w tym wartościowaniu formuła $\psi$ powstała z $\varphi$ przez zastąpienie klauzuli $C_j$ formułą $D_j$ jest również spełniona. I na odwrót, jeśli pewne wartościowanie spełnia formułę $\psi$, to aby $D_j$ było prawdziwe $x_1$ lub $x_2$ musi mieć wartość 1, a zatem to samo wartościowanie (bez zmiennej $y$) spełnia formułę $\varphi$.

Analogicznie, jesli $C_j$ 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 $k$ 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.

Dowód

Konstruujemy redukcję z problemu 3SAT. Na wejściu mamy formułę $\varphi =C_1\vee ...\vee C_m$. Każdą klauzulę $C_j=a\vee b\vee c$ przekształcamy w zbiór 10 klauzul, dla wygody rozważań podzielonych na trzy grupy, następujacej postaci:

1. $(a)(b)(c)(z)$

1. $(\mathrm{\neg }a\vee \mathrm{\neg }b)(\mathrm{\neg }b\vee \mathrm{\neg }c)(\mathrm{\neg }a\vee \mathrm{\neg }c)$

1. $(a\vee \mathrm{\neg }z)(b\vee \mathrm{\neg }z)(c\vee \mathrm{\neg }z)$

Tych 10 klauzul ma następujace własności:

1. Jeśli $a=b=c=0$, to niezależnie od wartości zmiennej $z$ co najwyżej 6 klauzul jest spełnionych.

1. Jeśli któryś z literałów $a$, $b$ lub $c$ jest równy 1, to

można dobrać wartość $z$ tak, że 7 klauzul jest spełnionych. Można sie o tym przekonać analizując wszystkie przypadki. Na przykład, jeśli $a=1$, $b=c=0$, to kładziemy $z=0$; jeśli $a=b=1$, $c=0$, to również kładziemy $z=0$, jeśli natomiast $a=b=c=1$ to 7 klauzul jest spełnionych gdy $z=1$.

Pozostaje zdefiniować żądaną liczbę spełnionych klauzul w formule wynikowej na $7m$. Z wymienionych własności wynika, że formuła wynikowa posiada wartościowanie spełniające dokładnie $7m$ 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 $G=(V,E)$ mówimy, że podzbiór $V^{\prime }\subseteq V$ jest pokryciem wierzchołkowym, jeśli każda krawędź w G ma co najmniej jeden z końców w zbiorze $V^{\prime }$.

Problem NODE COVER

Wejście: Graf nieskierowany $G=(V,E)$, liczba całkowita $k\le |V|$

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.

Dowód

Dla podanego podzbioru zbioru wierzchołków bardzo łatwo sprawdzić czy stanowi on pokrycie, zatem $NODECOVER\in NP$.

Redukujemy problem 3SAT do NODE COVER. Na wejściu mamy formułę $\varphi =C_1\wedge ...\wedge C_m$, i zgodnie z uwagą poczyniona przy dowodzie NP-zupełności 3SAT zakładamy, że każda alternatywa $C_j$ 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 $k=2m$.

rys_5_1.jpg(Redukcja 3SAT do NODE COVER)

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 $k$. 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 $v$ 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 $v$, prowadzi do pewnego wierzchołka $w$ odpowiadającego zaprzeczeniu literału wierzchołka $v$, zatem literał wierzchołka $w$ ma wartość zero i $w$ jest wybrane do pokrycia w trójkącie w którym występuje. Zatem krawędź $(v,w)$ 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 $n$, co kończy dowód.

Klika, zbiór niezależny

Przypomnijmy definicje obu problemów:

Problem [INDEPENDENT SET]

Wejście: Graf nieskierowany $G=(V,E)$, liczba całkowita $k\le |V|$

Wyjście: TAK jeśli $G$ ma zbiór niezależny (indukowany podgraf bez krawędzi) o $k$ wierzchołkach, NIE w przeciwnym przypadku.

Problem [CLIQUE]

Wejście: Graf nieskierowany $G=(V,E)$, liczba całkowita $k\le |V|$

Wyjście: TAK jeśli $G$ ma podgraf pełny (klikę) o $k$ wierzchołkach, NIE w przeciwnym przypadku.

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

{{cwiczenie|| Wykaż, że problem CLIQUE jest NP-zupełny.

Wskazówka:

Rozważ dopełnienie grafu.

Rozwiązanie:

Redukcja z problemu INDEPENDENT SET. Graf wynikowy

jest dopełnieniem grafu źródłowego, a parametr Parser nie mógł rozpoznać (błąd składni): {\displaystyle k<math> ma tę sama wartość. </div></div> }} ===Cykl i ścieżka Hamiltona=== \bigskip \noindent {\bf Problem} HAMILTONIAN CYCLE\\ {\it Wejście:} Graf nieskierowany <math>G=(V,E)<math>\\ {\it 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|[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 |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 {\em 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) E<math> gadżetu <math>G_{uv}=(V_{uv}, E_{uv})<math> będącego grafem przedstawionym na rysunku 5.2. \vspace{1cm} \begincenter \includegraphics[width=12cm]{rys_5_2.jpg}\\ \endcenter \vspace{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>. \vspace{1cm} \begincenter \includegraphics[width=12cm]{rys_5_3.jpg}\\ \endcenter \vspace{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 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 \[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>. _S=(s_i,[v,u_v^1,1]):v V, 1 i k (s_i,[v,u_v^d(v),6]):v V, 1 i k<center><math> Kładziemy zatem \[V'=\bigcup_{(uv)\in E}V_{uv}\cup\{s_j, 1\leq j\leq k\}<math></center> '=_{(uv) E}E_{uv} _{v V}E_v E_S<center><math> \vspace{1cm} \begincenter \includegraphics[width=12cm]{rys_5_4.jpg}\\ \endcenter \vspace{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 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>_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|[Uzupelnij]|| Problem HAMILTONIAN PATH jest NP-zupełny. }} ====section==== 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. \hint{Należy "wymusić" rozpoczęcie i zakończenie ścieżki dodatkowymi selektorami} \solution{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.} ====section==== Metoda 2: Skonstruuj redukcję z problemu CYKL HAMILTONA. \hint{Dodaj nowe wierzchołki które będą końcami ścieżki Hamiltona i powiąż je odpowiednio z innym wierzchołkami.} \solution{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.} ==Problemy na zbiorach i liczbach== ===Trójdzielne skojarzenie i pokrycie zbiorami=== Uogólnieniem klasycznego problemu skojarzenia w grafie dwudzielnym jest następujący problem: \bigskip \noindent {\bf Problem }TRIPARTITE MATCHING\\ {\it Wejście: }parami rozłączne równoliczne zbiory <math>W,X,Y<math> o mocy <math>p>0<math> oraz relacja <math>R W X Y<math>\\ {\it Wyjście: }TAK, jeśli istnieje skojarzenie w <math>R<math>, czyli podzbiór <math>R' R<math> taki, że dla dowolnych trójek <math>(w,x,y),(w',x',y') R<math> zachodzi <math>w w'<math>, <math>x x'<math> oraz <math>y y'<math>. NIE w przeciwnym przypadku.\\ 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=_1,...,C_m<math> nad zmiennymi <math>U=_1,...,u_n<math>. Najpierw dla każdej zmiennej <math>u 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: \[T_u^t=\{(w_{2j}^u,x_j^u,y_j^u), 1\leq j\leq m\}<math></center> _u^f=(w_{2j+1}^u,x_{j+1}^u,y_j^u), 1 j<m(w_1^u,x_1^u,y_m^u)<center><math> 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 \vspace{1cm} \begincenter \includegraphics[width=12cm]{rys_5_5.jpg}\\ \endcenter \vspace{1cm} Dla każdego gadżetu pierwsze elementy trójek, <math>w_1^u,...,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 {\it false} i pozostawi niepokryte elementy <math>w<math> o indeksach parzystych. Wybór przeciwny ustali wartościowanie <math>u<math> na {\it 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 q_j 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= 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 {\it 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 {\it 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: \[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> ====section==== 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> ====section==== 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} elementów, dla każdego elementu $a\in A$ waga $s(a)\in Z^{+}$ oraz liczba $B\in Z^{+}$.
Wyjście: TAK jeśli istnieje podzbiór $A^{\prime }\subseteq A$ taki że $\sum _{a\in A^{\prime }}s(a)=B$, NIE w przeciwnym przypadku.

Twierdzenie [Uzupelnij]

Problem SUBSET SUM jest NP-zupełny.

Dowód [Uzupelnij]

Skonstruujemy redukcję z problemu EXACT COVER BY 3 SETS. Na wejściu mamy zatem zbiór $X$ o liczności $3m$ i rodzinę $F=\{U_1,\dots ,U_n\}$ jego podzbiorów. Naszym zadaniem jest skonstruować zbiór $Y$ elementów z pewnymi wagami oraz liczbę B taką, że istnienie podzbioru w $Y$ o sumie wag elementów równej $B$ "wymusza" istnienie pokrycia zbioru $X$ wybranymi rozłącznymi podzbiorami z rodziny $F$.

Niech $p=\lceil {\log }_2(n+1)\rceil$. Najpierw ustalamy porządek elementów w zbiorze $|X|$ i zapisujemy każdy zbiór $U_j$ jako wektor $3m$-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 $p-1$ bitów zerowych i traktujemy ten wektor kjako liczbe zapisaną binarnie. Powstaje w ten sposób $n$ liczb $3mp$-bitowych -- są to wagi elementów zbioru Y. Liczba $B$ jest również takiej długości, powstaje przez wypisanie $3m$ jedynek a następnie wstawienie przed każdą jedynką $p-1$ zer.

Jeśli istnieje podrodzina $F^{\prime }\subseteq F$ stanowiąca rozłączne pokrycie zbioru $X$, to wektory bitowe poszczególnych trójek z $F^{\prime }$ arytmetycznie sumują sie do $B$, a na żadnej pozycji nie występuje przeniesienie. Zatem z istnienia pokrycia wynika istnienie podzbioru dającego w sumie wagę $B$.

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 $B$, to wszystkie te liczby w swoich rozwinięciach binarnych zawierają w sumie tyle jedynek ile jest ich w $B$, na różnych pozycjach. A więc odpowiadajace tym liczbom podzbiory pokrywają cały zbiór $X$.

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ł)
Wejście: Skończony zbiór $A$ elementów oraz dodatnia całkowita waga $s(a)$ każdego elementu
Wyjście: TAK jeśli istnieje podzbiór $A^{\prime }\subseteq A$ taki że $\sum _{a\in A^{\prime }}s(a)=\sum _{a\in A-A^{\prime }}s(a)$, NIE w przeciwnym przypadku.

section

Wykaż NP-zupełność problemu podziału.

Wskazówka

Skorzystaj z SUBSET SUM. Wystarczy dodać dwa elementy o odpowiednio dobranej dużej wadze.

Rozwiązanie

Niech $S=\sum _{a\in A}s(a)$. Dodajemy do zbioru dwa elementy $b_1$ i $b_2$, $s(b_1)=2S-B,s(b_2)=S+B$. Łatwo sprawdzić, że:

• Jeśli w zbiorze $A$ istnieje podzbiór $A^{\prime }$ o sumie równej $B$,

to podzbiór ten z dołączonym elementem $b_1$ daje sumę równą $2S$, tyle co pozostałe elementy uzupełnione o $b_2$.

• jeśli w zbiorze $A\cup \{b_1,b_2\}$ istnieje podział na 2

podzbiory o jednakowych wagach, to elementy $b_1$ i $b_2$ sa w różnych podzbiorach, bo ich wagi sumują się do $3S$. W tym podzbiorze do którego należy $b_1$ suma wag pozostałych elementów wynosi $B$.

Problem KNAPSACK (plecak)
Wejście: Skończony zbiór $A$ elementów, rozmiar $s(a)\in Z^{+}$ i wartość $v(a)\in Z^{+}$ dla każdego elementu, ograniczenie pojemności $B\in Z^{+}$ oraz żądana wartość $K\in Z^{+}$
Wyjście: TAK jeśli istnieje podzbiór $A^{\prime }\subseteq A$ taki że $\sum _{a\in A^{\prime }}s(a)\le B$ oraz $\sum _{a\in A}v(a)\ge K$, NIE w przeciwnym przypadku.

section

Pokaż że KNAPSACK jest NP-zupełny.

Wskazówka

Wykorzystaj SUBSET SUM lub PARTITION.

Rozwiązanie

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.

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
Wejście: $G_1=(V_1,E_1)$, $G_2=(V_2,E_2)$ - grafy nieskierowane
Wyjście: TAK jeśli $G_1$ ma podgraf izomorficzny z $G_2$, NIE w przeciwnym przypadku.

Wskazówka

Istnieje redukcja najprostszego typu z jednego z analizowanych powyżej problemów.

Rozwiązanie

Jest to proste ugólnienie problemu CLIQUE: szczególnym przypadkiem podgrafu o który pytamy w problemie SUBGRAPH ISOMORPHISM jest klika o liczności $k$ o która pytamy w problemie CLIQUE.

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
Wejście: Zbiór zadań $T$, dla każdego zadania $t$ trzy liczby całkowite: długość zadania $l(t)>0$, moment pojawienia się $r(t)\ge 0$,oraz ograniczenie czasowe $d(t)>0$
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 $A$ przydzielająca każdemu zadaniu $t$ czas rozpoczęcia wykonywania $A(t)$ taki, że $[A(t),A(t)+l(t)]\subseteq [r(t),d(t)]$ oraz $[A(t),A(t)+l(t))\cap [A(t^{\prime }),A(t^{\prime })+l(t^{\prime }))=\mathrm{\varnothing }$, dla każdego zadania $t^{\prime }\ne t$.

Wskazówka

Spróbuj, układając na prostej (osi liczbowej) odpowiednio zdefiniowany ciąg odcinków (zadań), wymusić istnienie podzbioru o zadanej sumie.

Rozwiązanie

Redukcja z problemu SUBSET SUM za pomocą bardzo prostych gadżetów. Niech $s_1,\dots ,s_n$ oraz $B$ będą odpowiednio wagami elementów oraz żądana sumą podzbioru elementów. Niech $D=\sum _{i=1}^n{s}_i$. Konstruujemy $n+1$ zadań, przy czym dla $i=1,\dots ,n$ zadanie $t_i$ ma długość $l_i=s_i$, czas gotowości $r_i=0$ oraz granicę $d_i=D+1$. Zadanie $t_{n+})$ jest "wymuszaczem podziału", o parametrach $l_i=1$, $r_i=B$, $d_i=B+1$.

Zadania $s_1,\dots ,s_n$ 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, $B$. 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ść $B$, 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 $B$.

section

Problem cięcia w grafie zdefiniowany jest następująco:

Problem FEEDBACK VERTEX SET
Wejście: Graf skierowany $G=(V,E)$, liczba całkowita $k,0<k\ge |V|$.
Wyjście: TAK jeśli istnieje w $G$ podzbiór $k$-wierzchołkowy, taki że graf pozostały po usunięciu tego podzbioru jest acykliczny.
Udowodnij, że FEEDBACK VERTEX SET jest NP-zupełny.

Wskazówka

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?

Rozwiązanie

Na wejściu mamy graf nieskierowany $G=(V,E)$ i liczbę $k$. Zamieniamy ten graf na graf skierowany $G^{\prime }$, z tym samym zbiorem wierzchołków, zastępując każdą krawędź nieskierowaną $(u,v)$ przez dwie krawędzie skierowane: $(u,v)$ oraz $(v,u)$. Liczba $k$ jest taka sama dla obu instancji.

Nietrudno zauważyć, że każde pokrycie wierzchołkowe w $G$ jest zbiorem rozcinającym wszystkie cykle w $G^{\prime }$ i na odwrót.

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
Wejście: Graf nieskierowany $G=(V,E)$.
Wyjście: TAK, jeśli istnieje funkcja $c:V\to \{0,1,2\}$ taka, że dla każdej krawędzi $(u,v)\in E$, $c(u)\ne c(v)$.
Za pomocą redukcji z problemu 3SAT udowodnij, że problem trójkolorowania jest NP-zupełny.

Wskazówka

Można użyć gadżetu przedstawionego na rysunku 5.6. {1cm}

[width=12cm]{rys_5_6.jpg}

{1cm} UWAGA DLA REDAKCJI: RYSUNEK POJAWIA SIĘ JAKO CZĘŚĆ WSKAZÓWKI

Rozwiązanie

Gadżet ma następujące własności:

• jeśli wierzchołkom $u,v,z$ 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 $c(z)=1$

• jeśli w danym trójkolorowaniu $c(u)=c(v)=c(z)=0$, to

również $c(z)=0$.

Redukcję przeprowadzamy następująco:

1. generujemy wierzchołki $s,t,z$ i trójkat oparty na nich

1. Dla każdej zmiennej $x$ występującej w instancji 3SAT definiujemy

wierzchołki $x,\mathrm{\neg }x$ oraz trójkąt oparty na $x,\mathrm{\neg }x$ oraz $t$

1. dla każdej klauzuli $C_j=(u\vee v\vee w)$ definiujemy kopię gadżetu,

przy czym wierzchołki $u,v,w$ to już wygenerowane w punkcie 2 wierzchołki literałów o tych samych nazwach, wierzchołek $z$ został wygenerowany w kroku 1, natomiast pozostałe wierzchołki są nowe, unikalne dla każdej klauzuli

{1cm}

[width=12cm]{rys_5_7.jpg}

{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 $c(s)=0$, $c(z)=1$ $c(t)=2$

• kolorujemy każdy z wierzchołków $x_i,\mathrm{\neg }{x}_i$ 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 $s,t,z$ są różne, więc umawiamy się, że $c(s)=0,c(t)=2,c(z)=1$

• dla każdej zmiennej $x_i$ kładziemy wartość tej zmiennej równą

$c(x_i)$. Ponieważ $c(t)=2$ więc wartość ta wynosi 0 lub 1.

Ponieważ $c(z)=1$, 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ę.