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 </math>G=(V,E)Parser nie mógł rozpoznać (błąd składni): {\displaystyle mówimy, że podzbiór } V' VParser nie mógł rozpoznać (błąd składni): {\displaystyle jest pokryciem wierzchołkowym, jeśli każda krawędź w G ma co najmniej jeden z końców w zbiorze } V'Parser nie mógł rozpoznać (nieznana funkcja „\bigskip”): {\displaystyle . \bigskip \noindent {\bf Problem} NODE COVER\\ {\it Wejście:} Graf nieskierowany } G=(V,E)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , liczba całkowita } k |V|Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ {\it 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 } { NODE COVER} NPParser nie mógł rozpoznać (błąd składni): {\displaystyle . Redukujemy problem 3SAT do NODE COVER. Na wejściu mamy formułę } =C_1 ... C_mParser nie mógł rozpoznać (błąd składni): {\displaystyle , i zgodnie z uwagą poczyniona przy dowodzie NP-zupełności 3SAT zakładamy, że każda alternatywa } C_jParser nie mógł rozpoznać (błąd składni): {\displaystyle 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=2mParser nie mógł rozpoznać (nieznana funkcja „\vspace”): {\displaystyle . \vspace{1cm} \begincenter \includegraphics[width=12cm]{rys_5_1.jpg}\\ Redukcja 3SAT do NODE COVER \endcenter \vspace{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 } kParser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 } vParser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } vParser nie mógł rozpoznać (błąd składni): {\displaystyle , prowadzi do pewnego wierzchołka } wParser nie mógł rozpoznać (błąd składni): {\displaystyle odpowiadającego zaprzeczeniu literału wierzchołka } vParser nie mógł rozpoznać (błąd składni): {\displaystyle , zatem literał wierzchołka } wParser nie mógł rozpoznać (błąd składni): {\displaystyle ma wartość zero i } wParser nie mógł rozpoznać (błąd składni): {\displaystyle jest wybrane do pokrycia w trójkącie w którym występuje. Zatem krawędź } (v, w)Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } nParser nie mógł rozpoznać (błąd składni): {\displaystyle , co kończy dowód. }} ===Klika, zbiór niezależny=== Przypomnijmy definicje obu problemów: \bigskip \noindent {\bf Problem} INDEPENDENT SET\\ {\it Wejście:} Graf nieskierowany } G=(V,E)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , liczba całkowita } k |V|Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ {\it Wyjście}: TAK jeśli } GParser nie mógł rozpoznać (błąd składni): {\displaystyle ma zbiór niezależny (indukowany podgraf bez krawędzi) o } kParser nie mógł rozpoznać (błąd składni): {\displaystyle wierzchołkach, NIE w przeciwnym przypadku. \bigskip \noindent {\bf Problem} CLIQUE\\ {\it Wejście:} Graf nieskierowany } G=(V,E)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , liczba całkowita } k

|V|Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ {\it Wyjście}: TAK jeśli } GParser nie mógł rozpoznać (błąd składni): {\displaystyle ma podgraf pełny (klikę) o } kParser nie mógł rozpoznać (błąd składni): {\displaystyle wierzchołkach, NIE w przeciwnym przypadku. ====section==== Wykaż, że problem INDEPENDENT SET jest NP-zupełny. \beginhintJeśli } V'Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest pokryciem wierzchołkowym, to jaką własność ma zbiór } V-V'Parser nie mógł rozpoznać (nieznana funkcja „\beginsolutionDope”): {\displaystyle ? </div></div> \beginsolutionDopełnienie pokrycia jest oczywiście zbiorem niezależnym. Zatem redukcja z problemu NODE COVER, mając na wejściu graf } G=(V,E)Parser nie mógł rozpoznać (błąd składni): {\displaystyle i liczbę } kParser nie mógł rozpoznać (błąd składni): {\displaystyle generuje instancję } G'=(V',E'),k'Parser nie mógł rozpoznać (błąd składni): {\displaystyle problemu INDEPENDENT SET, kładąc } G'=G

$,$

k'=|V|-kParser nie mógł rozpoznać (błąd składni): {\displaystyle . </div></div> ====section==== 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. ====section==== Wykaż, że problem CLIQUE jest NP-zupełny. \beginhintRozważ dopełnienie grafu. </div></div> \beginsolutionRedukcja z problemu INDEPENDENT SET. Graf wynikowy jest dopełnieniem grafu źródłowego, a parametr } kParser nie mógł rozpoznać (błąd składni): {\displaystyle ma tę sama wartość. </div></div> ===Cykl i ścieżka Hamiltona=== \bigskip \noindent {\bf Problem} HAMILTONIAN CYCLE\\ {\it Wejście:} Graf nieskierowany } G=(V,E)Parser nie mógł rozpoznać (błąd składni): {\displaystyle \\ {\it Wyjście}: TAK jeśli } GParser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } G=(V,E)Parser nie mógł rozpoznać (błąd składni): {\displaystyle oraz liczbę całkowitą } k |V|

$.Oznaczmygrafwynikowyjako$

G'=(V',E')Parser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 } (u,v) EParser nie mógł rozpoznać (błąd składni): {\displaystyle gadżetu } G_{uv}=(V_{uv}, E_{uv})Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } G_{uv}Parser nie mógł rozpoznać (błąd składni): {\displaystyle będą połączone z wierzchołkami spoza } G_{uv}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Stąd wynika, że jeśli } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle ma cykl Hamiltona, to musi on przechodzić przez } G_{uv}Parser nie mógł rozpoznać (błąd składni): {\displaystyle tylko na jeden z przedstawionych na rysunku 5.3 sposobów. Konstrukcja gadżetu uniemożliwia inne usytuowanie cyklu Hamiltona względem } G_{uv}Parser nie mógł rozpoznać (nieznana funkcja „\vspace”): {\displaystyle . \vspace{1cm} \begincenter \includegraphics[width=12cm]{rys_5_3.jpg}\\ \endcenter \vspace{1cm} Drugi krok redukcji to wygenerowanie krawędzi w } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle łączących gadżety w tak zwane ścieżki. Dla każdego wierzchołka } v VParser nie mógł rozpoznać (błąd składni): {\displaystyle najpierw porządkujemy dowolnie wszystkie jego sąsiednie wierzchołki, oznaczmy je przez } u_v^1,...,u_v^{d(v)}

$,gdzie$

d(v)Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest stopniem wierzchołka } vParser nie mógł rozpoznać (błąd składni): {\displaystyle . Konstrukcja ścieżki odpowiadającej wierzchołkowi } vParser nie mógł rozpoznać (błąd składni): {\displaystyle , łączącej wszystkie gadżety odpowiadające krawędziom incydentnym z } vParser nie mógł rozpoznać (błąd składni): {\displaystyle , dokonuje sie przez dołączenie do } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle zbioru krawędzi postaci \[E_v=\{([v,u_v^i,6],[v,u_v^{i+1},1]), i=1,\ldots,d(v)-1\}}

Ostatni krok to dodanie wierzchołków-selektorów $s_1,\dots ,s_k$, i połączenie krawędzią każdego selektora z początkiem i końcem ścieżki odpowiadającej wierzchołkowi $v$, dla każdego $v$.

_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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Kładziemy zatem \[V'=\bigcup_{(uv)\in E}V_{uv}\cup\{s_j, 1\leq j\leq k\}}

'=_{(uv) E}E_{uv} _{v V}E_v E_S

Parser nie mógł rozpoznać (nieznana funkcja „\vspace”): {\displaystyle \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 } s_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle przechodzimy do początku ścieżki odpowiadającej pierwszemu wierzchołkowi z pokrycia, czyli } xParser nie mógł rozpoznać (błąd składni): {\displaystyle . Po przejściu gadżetów na tej ścieżce wracamy do } s_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a stąd do początku ścieżki odpowiadajacej drugiemu węzłowi z pokrycia, } yParser nie mógł rozpoznać (błąd składni): {\displaystyle . Wykażemy, że } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle ma cykl Hamiltona wtedy i tylko wtedy gdy G ma pokrycie o liczności } kParser nie mógł rozpoznać (błąd składni): {\displaystyle . Załóżmy, że } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle ma cykl Hamiltona i prześledźmy jego bieg zaczynając od } s_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle (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 } v_1 V$.Dodajemy$v_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } s_2$.Z$s_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle musi przejść na początek lub koniec innej ścieżki, odpowiadającej wierzchołkowi } v_2$.Dodajemy$v_2$dopokryciaikontynuujemy.Zostatniej,$kParser nie mógł rozpoznać (błąd składni): {\displaystyle -tej ścieżki, cykl musi wrócić do } s_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ponieważ cykl Hamiltona przeszedł przez wszystkie wierzchołki } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle , a więc przez wszystkie gadżety } G_{uv}Parser nie mógł rozpoznać (błąd składni): {\displaystyle , zatem wybrane w ten sposób wierzchołki } v_1,...,v_kParser nie mógł rozpoznać (błąd składni): {\displaystyle stanowią pokrycie. Teraz załóżmy, że } G$mapokrycie$_1,...,v_k$.KonstruujemycyklHamiltonaw$G'$.Zaczynamyodselektora$s_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle i przechodzimy na początek ścieżki związanej z } v_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle , czyli do węzła } [v_1,u_{v_1}^1,1]Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Przechodzimy przez kolejne gadżety aż do końca ścieżki. Dla danego gadżetu } G_{v_1u_{v_1}^i}Parser nie mógł rozpoznać (błąd składni): {\displaystyle musimy podjąć decyzję czy przechodzimy przez wszystkie wierzchołki czy tylko przez połowę (jedną "ścianę"). Decyzja zależy od tego czy } u_{v_1}^iParser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } u_{v_1}^iParser nie mógł rozpoznać (błąd składni): {\displaystyle również można było przejść przez } G_{v_1u_{v_1}^i}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Z ostatniego węzła na ścieżce przechodzimy do selektora } s_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle i powtarzamy konstrukcję. Z ostatniego węzła na } kParser nie mógł rozpoznać (błąd składni): {\displaystyle -tej ścieżce wracamy do } s_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle , zamykając w ten sposób cykl Hamiltona. Ostatnim krokiem dowodu jest stwierdzenie, że konstrukcję grafu } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle . }} 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 } G'Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } s_0Parser nie mógł rozpoznać (błąd składni): {\displaystyle i łączymy go krawędzią z } s_1Parser nie mógł rozpoznać (błąd składni): {\displaystyle . następnie dodajemy selektor } s_{k+1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle i łączymy go z początkami i końcami wszystkich ścieżek. na koniec dodajemy } s_{k+2}Parser nie mógł rozpoznać (błąd składni): {\displaystyle i łączymy go z } s_{k+1}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Jeśli graf wynikowy posiada ścieżkę Hamiltona, to jej końcami muszą być selektory } s_0$i$s_{k+2}Parser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 } vParser nie mógł rozpoznać (błąd składni): {\displaystyle , utworzyć wierzchołek } v'Parser nie mógł rozpoznać (błąd składni): {\displaystyle o takim samym zbiorze sąsiadów w grafie (inaczej: rozszczepić v na dwa identyczne), a nastepnie dołączyć nowy wierzchołek } u_1$do$v$ijeszczejedennowy$u_2$do$v'Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Łatwo sie przekonać że w nowym grafie istnieje ścieżka Hamiltona (koniecznie o końcach } u_1, u_2Parser nie mógł rozpoznać (błąd składni): {\displaystyle ) 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 } W,X,Y$omocy$p>0$orazrelacja$R W X YParser nie mógł rozpoznać (błąd składni): {\displaystyle \\ {\it Wyjście: }TAK, jeśli istnieje skojarzenie w } RParser nie mógł rozpoznać (błąd składni): {\displaystyle , czyli podzbiór } R' RParser nie mógł rozpoznać (błąd składni): {\displaystyle taki, że dla dowolnych trójek } (w,x,y),(w',x',y') R$zachodzi$w w'$,$x x'$oraz$y y'Parser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 } C=_1,...,C_m$nadzmiennymi$U=_1,...,u_nParser nie mógł rozpoznać (błąd składni): {\displaystyle . Najpierw dla każdej zmiennej } u UParser nie mógł rozpoznać (błąd składni): {\displaystyle konstruujemy gadżet } T_uParser nie mógł rozpoznać (błąd składni): {\displaystyle , 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\}}

_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)

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Przykładowy gadżet dla zmiennej } u$,wprzypadkugdyliczbaklauzulwynosi$m=4Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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, } w_1^u,...,w_m^uParser nie mógł rozpoznać (błąd składni): {\displaystyle , 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 } T_u^fParser nie mógł rozpoznać (błąd składni): {\displaystyle i żadnej trójki z } T_u^tParser nie mógł rozpoznać (błąd składni): {\displaystyle , albo na odwrót. W toku dalszego rozumowania, wybór do skojarzenia zbioru } T_u^fParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie oznaczał wartościowanie zmiennej } u$na{f}{a}{l}{s}{e}ipozostawiniepokryteelementy$wParser nie mógł rozpoznać (błąd składni): {\displaystyle o indeksach parzystych. Wybór przeciwny ustali wartościowanie } u$na{t}{r}{u}{e}ipozostawiniepokryteelementy$wParser nie mógł rozpoznać (błąd składni): {\displaystyle o indeksach nieparzystych. Sytuacja taka została przedstawiona na rysunku 5.5, pogrubioną linią zaznaczono wybór trójek } T_u^tParser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 } C_j=(p_j q_j r_j)Parser nie mógł rozpoznać (błąd składni): {\displaystyle składowa testowania } S_jParser nie mógł rozpoznać (błąd składni): {\displaystyle zawiera 3 trójki } s_j^1,s_j^2,s_j^3Parser nie mógł rozpoznać (błąd składni): {\displaystyle odpowiadajace kolejnym literałom } p,q,rParser nie mógł rozpoznać (błąd składni): {\displaystyle , zdefiniowane następująco: Jeśli } p=u_i$to$s_j^1=(w_{2j-1}^u,a_j, b_j)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Jeśli } p= u_i$to$s_j^1=(w_{2j}^u,a_j,b_j)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Analogicznie dla literałów } q, r$.Elementy$a_j, b_jParser nie mógł rozpoznać (błąd składni): {\displaystyle występują tylko w trzech trójkach zbioru } S_jParser nie mógł rozpoznać (błąd składni): {\displaystyle , 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 } C_jParser nie mógł rozpoznać (błąd składni): {\displaystyle jest spełniona. Innymi słowy, możliwość pokrycia elementów } a_j, b_jParser nie mógł rozpoznać (błąd składni): {\displaystyle jest równoważna temu, że istnieje w klauzuli } C_jParser nie mógł rozpoznać (błąd składni): {\displaystyle literał o wartości logicznej {\it true}. Skojarzenie wybrane dla gadżetów ma liczność } nmParser nie mógł rozpoznać (błąd składni): {\displaystyle , składowa testowania daje kolejnych } mParser nie mógł rozpoznać (błąd składni): {\displaystyle trójek w skojarzeniu, zatem ze wszystkich } 2nmParser nie mógł rozpoznać (błąd składni): {\displaystyle elementów na pierwszej współrzędnej (elementy } u$)$(n-1)mParser nie mógł rozpoznać (błąd składni): {\displaystyle 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\}}

Pozwala ona skojarzyć elementy $u$ 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)
Wejście: Rodzina ${ℱ}$ trójelementowych podzbiorów zbioru $X$ takiego że $|X|=3k$ dla pewnej calkowitej $k$
Wyjście: TAK jesli istnieje podrodzina ${{ℱ}}^{\prime }{\subseteq }{ℱ}$ taka, że każdy element zbioru $X$ należy do dokładnie jednego zbioru rodziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cal F"} , NIE w przeciwnym przypadku

section

Wykaż że EXACT COVER BY 3-SETS jest NP-zupełny.

Rozwiązanie

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 $F$ 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.

Problem SET COVERING (pokrycie zbiorami)
Wejście: Rodzina $F=\{S_1,\dots ,S_n\}$ podzbiorów zbioru $|X|$, liczba całkowita $k\le n$
Wyjście: TAK, jeśli istnieje k-elementowa podrodzina rodziny $F$, która pokrywa cały zbiór $|X|$, w przeciwnym przypadku NIE.

section

Wykaż NP-zupełność problemu SET COVERING.

Rozwiązanie

Ponownie przez ograniczenie do podproblemu: jeśli założymy że $|X|=3k$ a wszystkie zbiory rodziny $F$ są 3-elementowe, to otrzymujemy problem EXACT COVER BY 3-SETS.

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)
Wejście: Skończony zbiór $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ę.