Złożoność obliczeniowa/Wykład 6: NP-zupełność jako narzędzie analizy problemu

Wstęp

Upraszczanie problemu przez narzucanie dodatkowych warunków na jego

instancje może zmniejszyć jego złożoność. Na tej lekcji poznamy

ciekawe przypadki, gdy po zacieśnieniu problem staje się

obliczeniowo łatwy, jak i sytuacje przeciwne, gdy nawet mocne

ograniczenia nie likwidują NP-zupełności. Poznamy również pojęcie

silnej NP-zupełności, pozwalające abstrahować od wpływu wielkości

liczb na trudność obliczeniową, a także uniezależniające trudność

problemu od sposobu kodowania liczb.

Ciekawe podproblemy

Spełnialność

Na poprzedniej lekcji zauważyliśmy, że im prostszy problem źródłowy,

tym łatwiej skonstruować redukcję z tego problemu do innego. Wiemy,

że jednym z podstawowych problemów służących jako początek redukcji

jest 3SAT. Naturalne jest zatem pytanie, czy dalsze zawężenia

problemu SAT polegające na skracaniu klauzul zachowują NP-zupełność.

Oczywiste jest, że 1SAT to problem trywialny -- na wejściu jest po

prostu koniunkcja literałów -- pozostaje zatem 2SAT. Przypomnijmy,

że oznacza to, iż każda alternatywa jest co najwyżej dwuskładnikowa,

a dodatkowo załóżmy, że jeśli jest tylko jeden składnik, to

powielamy go. Zatem każda alternatywa jest długości dwa.

Twierdzenie

Problem 2SAT jest rozwiązywalny w czasie wielomianowym.

Dowód

Każdą alternatywę $C_j=x_1\vee x_2$ można traktować jako

implikację $\mathrm{\neg }{x}_1\Rightarrow x_2$. Rozważmy zatem graf

skierowany $G(\varphi )$ dla wejściowej formuły $\varphi$ zbudowany

następująco:

• dla każdej zmiennej $x_i$ wstępującej w formule tworzymy dwa

wierzchołki: $x_i$ oraz $\mathrm{\neg }{x}_i$

• dla każdej alternatywy $C_j=u\vee v$ tworzymy dwie krawędzie:

$(\mathrm{\neg }u,v)$ oraz $(\mathrm{\neg }v,u)$

W ten sposób krawędzie grafu opisują implikacje logiczne zawarte w

formule $\varphi$: jeśli $C_j=u\vee v$ występuje w formule, i pewne

wartościowanie kładzie $u=0$ (czyli $\mathrm{\neg }u=1$), to w tym

wartościowaniu zachodzi $v=1$. Zatem jeśli początek krawędzi grafu

$G(\varphi )$ ma wartość 1, to koniec krawędzi również. Zauważmy, że

symetria w grafie, polegająca na tym, że istnieją obie krawędzie:

$(\mathrm{\neg }u,v)$ oraz $(\mathrm{\neg }v,u)$, odpowiada po prostu kontrapozycji w

każdej implikacji.

Rysunek 1 przedstawia $G(\varphi )$ dla przykładowej formuły

$\varphi =(\mathrm{\neg }{x}_1\vee \mathrm{\neg }{x}_2)\wedge (x_1\vee x_4)\wedge (x_2\vee x_3)\wedge (x_2\vee \mathrm{\neg }{x}_3)\wedge (\mathrm{\neg }{x}_2\vee \mathrm{\neg }{x}_4)$

[width=10cm]{ZO-6-rys-1.jpg}

Szukając wartościowania spełniającego tę formułę zacznijmy na

przykład od $x_2=1$. Od wierzchołka $x_2$ w grafie prowadzi ścieżka

do $\mathrm{\neg }{x}_2$, co oznacza że $\mathrm{\neg }{x}_2$ też musi mieć wartość 1,

zatem nie istnieje wartościowanie spełniające formułę $\varphi$, w

którym $x_2=1$. Ale jeśli położymy $x_2=0$, to, ponieważ istnieje

również ścieżka z $\mathrm{\neg }{x}_2$ do $x_2$, otrzymamy $x_2=1$. Więc nie

da się ustalić wartościowania dla $x_2$, a zatem i dla całej

formuły.

Z powyższego rozumowania łatwo można wyciągnąć następujący wniosek:

jeśli w grafie $G(\varphi )$ dla pewnej zmiennej $x_i$, wierzchołki

$x_i$ oraz $\mathrm{\neg }{x}_i$ należą do pewnego cyklu, to formuła $\varphi$ nie

jest spełnialna. Okazuje się, że prawdziwa jest również implikacja

odwrotna. Wykażemy mianowicie, że jeśli dla każdej zmiennej $x_i$,

wierzchołki $x_i$ oraz $\mathrm{\neg }{x}_i$ nie leżą na wspólnym cyklu, to

istnieje wartościowanie spełniające $\varphi$.

Zacznijmy od dowolnego wierzchołka $v$ takiego, że nie istnieje

ścieżka z $v$ do $\mathrm{\neg }v$. Z założenia wynika, że dla każdej

zmiennej $x_i$ co najmniej jeden z wierzchołków $x_i$ oraz $\mathrm{\neg }{x}_i$ posiada tę własność. Wszystkim wierzchołkom $u$ osiągalnym z

$v$ przypisujemy wartość 1. Negacjom tych wierzchołków przypisujemy

0, co odpowiada znajdowaniu wierzchołków osiągalnych z $\mathrm{\neg }v$

posuwając się wstecz (czyli: jedynkę propagujemy wprzód, zaś zero

cofając się po krawędziach grafu).

Nie jest możliwa sytuacja, że danemu wierzchołkowi $w$ przypisujemy

w tej procedurze różne wartości. Oznaczałoby to, że zarówno $w$ jak

i $\mathrm{\neg }w$ są osiągalne z $v$, co pociągałoby istnienie ścieżki z

$v$ do $\mathrm{\neg }v$.

Jeśli pozostał jakiś wierzchołek o nieprzypisanej wartości, to

powtarzamy procedurę, aż wartościowanie obejmie wszystkie

wierzchołki. Upewnijmy się jeszcze co do poprawności kolejnych

powtórzeń procedury, że nie zmieniają wartościowań ustalonych w

poprzednich iteracjach. Załóżmy, że w kolejnym przeglądzie grafu

istnieje krawędź od wierzchołka $s$ wartościowanego na 1 w tej

iteracji do pewnego wierzchołka $t$ wartościowanego we wcześniejszej

iteracji na 0, i że jest to pierwsza taka sytuacja. Zauważmy jednak,

że wartościowanie $t=0$ propaguje się przeciwnie do kierunku

krawędzi $(s,t)$, zatem już w poprzedniej iteracji musiło byc

ustalone $s=0$, sprzeczność. Analogicznie, nie występują zmiany

wartościowania z 1 na 0.

W takim razie obliczone wartościowanie spełnia wszystkie implikacje

opisane krawędziami grafu, a zatem spełnia formułę.

Pozostaje zauważyć, że wersję decyzyjną prolemu rozwiązuje się

stosując standardowy algorytm znajdowania silnie spójnych składowych

grafu skierowanego i sprawdzając czy w którejś składowej znajduje

się zarówno jakaś zmienna jak i jej zaprzeczenie. Formuła jest

spełnialna wtedy i tylko wtedy gdy dla każdego $i$, $x_i$ należy do

innej silnie spójnej składowej niż $\mathrm{\neg }{x}_i$. Algorytm ten ma

złożoność liniową. Można pokazać, że znajdowanie wartościowania

również jest wykonalne w czasie liniowym.

Długośc klauzuli, czyli liczba występujących w niej alternatyw, nie

jest jedyną cechą, która może podlegać restrykcji. Inne sensowne

zacieśnienie problemu SAT otrzymujemy ograniczając częstotliwość

występowania zmiennych i literałów w formule.

Problem 3OCCUR3SAT

Wejście: Formuła logiczna $\varphi$ w koniunkcyjnej postaci

normalnej taka, że w każdej alternatywie są co najwyżej 3 literały,

każda zmienna występuje nie więcej niż 3 razy, a każdy literał nie więcej niż 2 razy

Wyjście: TAK jeśli $\varphi$ jest spełnialna, NIE w przeciwnym

przypadku.

Udowodnij, że 3OCCUR3SAT jest NP-zupełny.

Wskazówka

Wystąpienia zmiennej, która pojawia się zbyt wiele razy, zastąp

odpowiednią liczbą nowych zmiennych i zapewnij, że są tak samo

wartościowane, jak zmienna którą zastępują.

Rozwiązanie

Załóżmy, że zmienna $x$ występuje $k$ razy w formule $\varphi$. Kolejne

wystąpienia $x$ zastępujemy nowymi zmiennymi $y_1,\dots ,y_k$ i

dodajemy ciąg implikacji $y_1\Rightarrow y_2\Rightarrow \dots \Rightarrow y_k\Rightarrow y_1$, czyli alternatywy $(\mathrm{\neg }{y}_1\vee y_2),(\mathrm{\neg }{y}_2\vee y_3),\dots ,(\mathrm{\neg }{y}_{k-1}\vee y_k),(\mathrm{\neg }{y}_k\vee y_1).$

Aby "przedłużyć" redukcję z powyższego ćwiczenia w celu otrzymania

formuł z klauzulami o długości dokładnie 3 nie możemy zastosować

podstawowej sztuczki polegającej na powieleniu literału w klauzuli,

ani też dodawania nowych zmiennych, jak to było stosowane w uwadze

do wariantów problemu 3SAT w poprzednim module. Nasuwa się pytanie

czy to, że w przeciwdziedzinie redukcji opisanej w rozwiązaniu

ćwiczenia istnieją alternatywy o długości 2, jest istotne.

Czy problem 3OCCUR 3SAT z dodatkowym założeniem, że każda

alternatywa zawiera 3 literały nad różnymi zmiennymi, jest

NP-zupełny? Oczywiście odpowiedź uzasadnij.

Pierwsza wskazówka podaje tylko odpowiedź tak/nie.

Wskazówka

Jest obliczeniowo łatwy (czyli jest NP-zupełny tylko jeśli P=NP).

Druga wskazówka sugeruje sposób uzasadnienia.

Wskazówka

Rozważ graf dwudzielny, w którym jedną grupę wierzchołków stanowią

klauzule, zaś drugą zmienne.

Rozwiązanie

Każdą klauzulę łączymy krawędziami z występującymi w niej zmiennymi.

Zatem stopień każdego wierzchołka-klauzuli wynosi 3, zaś stopień

każdego wierzchołka-zmiennej jest równy co najwyżej 3. Rozważmy

dowolny podzbiór $D$ zbioru klauzul oraz zbiór $Y$ zmiennych

występujących w tych klauzulach. Twierdzimy, że $|Y|\ge |D|$.

Mianowicie, jeśliby tak nie było, to ponieważ każda zmienna

występuje w co najwyżej 3 klauzulach, zbiór $Y$ nie wystarczałby do

zdefiniowania tylu klauzul, nawet gdyby te zmienne występowały tylko

w klauzulach z $D$.

Z twierdzenia Halla o systemach różnych reprezentantów (znanego z

kursu matematyki dyskretnej) wynika, że skonstruowany przez nas graf

dwudzielny ma skojarzenie o maksymalnej liczności, co oznacza że w

każdej klauzuli można wskazać zmienną i nadać jej wartość taką, aby

ta klauzula była spełniona w taki sposób, że wybrane zmienne są

różne dla różnych klauzul.

Wykazaliśmy zatem, że każda formuła spełniająca założenia jest

spełnialna. Zatem algorytm rozwiązujący ten decyzyjny problem, po

sprawdzeniu założeń po prostu odpowiada TAK.

Na zakończenie tego rozdziału omówimy jeszcze jedną z wersji

problemu SAT polegających na zacieśnieniu postaci formuły. Mówimy,

że klauzula jest hornowska, jeśli zawiera co najwyżej jeden literał

nie bedący negacją zmiennej (literał pozytywny). Taką klauzulę,

jeśli zawiera literał pozytywny, wygodnie jest traktować jako

implikację, np. $(\mathrm{\neg }{x}_1\vee \mathrm{\neg }{x}_2\vee x_3\vee \mathrm{\neg }{x}_4)$ jest

równoważna implikacji $((x_1\wedge x_2\wedge x_4)\Rightarrow x_3)$,

zaś klauzula $(x_i)$ jest równoważna $(0\Rightarrow x_i)$.

Problem HORNSAT

Wejście: Formuła $\varphi$ będąca koniunkcją klauzul hornowskich

Wyjście: TAK jeśli ta formuła jest spełnialna, NIE w przeciwnym przypadku

Twierdzenie

Problem HORNSAT jest obliczeniowo łatwy.

Dowód

Konstruujemy algorytm znajdujący wartościowanie spełniające daną

formułę, o ile takie istnieje. Wartościowanie to będzie utożsamiane

ze zbiorem $Y$ tych zmiennych, które mają przypisaną wartość 1.

Początkowo $Y=\mathrm{\varnothing }$. Jeśli w formule nie występują klauzule

jednoskładnikowe zawierające zmienną pozytywną, to wartościowanie

$Y$ spełnia formułę i algorytm się kończy.

W przeciwnym przypadku, dopóki nie wszystkie implikacje są spełnione

wykonuj następującą operację: wybierz dowolną implikację

$((x_1\wedge \dots \wedge x_k)\Rightarrow z)$, która jest

niespełniona, a więc wartości zmiennych $x_1,\dots ,x_k$ są

jedynkami, a wartość $z$ jest 0. Dodaj zmienną $z$ do zbioru $Y$.

Algorytm zatrzymuje się gdy nie ma niespełnionej implikacji.

Wykażemy, że jeśli formuła jest spełnialna, to wartościowanie $Y$ ją

spełnia.

Na początek zauważmy, że każde wartościowanie $W$ spełniające

formułę musi zawierać cały zbiór $Y$ na 1. W przeciwnym przypadku,

jeśli $x_i$ jest najwcześniej w algorytmie wartościowaną na 1

zmienną, taką że $x\in Y-W$, to jej poprzedniki w rozpatrywanej

implikacji należą do $W$, a więc w takiej sytuacji $W$ nie spełnia

tej implikacji, co stanowi sprzeczność.

Nasz algorytm się zatrzymuje gdy nie ma już niespełnionych

implikacji. Jeśli nadal istnieje niespełniona klauzula, to ma ona

postać alternatywy negacji zmiennych, np. $(\mathrm{\neg }{x}_1\wedge \dots \wedge \mathrm{\neg }{x}_k)$, i wszystkie te zmienne maja wartość

1. Ponieważ każde wartościowanie spełniające formułę musi być

nadzbiorem wartościowania $Y$, więc w takim przypadku nie istnieje

wartościowanie spełniające wszystkie klauzule. Zatem nasz algorytm

oblicza poprawnie wartościowanie spełniające formułę, o ile takie

wartościowanie istnieje.

Pozostaje zauważyć, że opisana procedura jest łatwo realizowalna w

czasie wielomianowym.

Klasyczne problemy grafowe

Teraz zajmiemy się analizą zacieśnień wybranych problemów grafowych.

Na początek odnotujmy kilka bardzo łatwych spostrzeżeń.

Twierdzenie

Jeśli graf podany na wejściu jest drzewem, to następujące problemy

są w P: HAMILTONIAN CYCLE, HAMILTONIAN PATH, CLIQUE, COLORING, NODE

COVER, INDEPENDENT SET.

Tylko problem pokrycia wierzchołkowego i równoważny mu problem

zbioru niezależnego wymagają naszkicowania algorytmu - pozostałe są

trywialne. Przypomnijmy, że dopełnienie pokrycia jest zbiorem

niezależnym, wystarczy więc zająć się na przykład tylko tym

ostatnim.

Skonstruuj wielomianowy algorytm znajdowania maksymalnego pod

względem liczności zbioru niezależnego w zadanym drzewie $T$.

Rozwiązanie

Ustalmy dowolnie korzeń $r$ w drzewie. Algorytm działa metodą

zachłanną, konstruując zbiór niezależny $S$ w następujący sposób.

Przeglądamy wierzchołki drzewa w kolejności postorder, i jeśli

wszystkie następniki danego wierzchołka nie należą do $S$, to ten

wierzchołek dodajemy do $S$.

Aby udowodnić, że skonstruowany zbiór niezależny jest maksymalny,

wystarczy rozważyć dowolny maksymalny zbiór niezależny $Q$.

Analizując jego wierzchołki w kolejności postorder i porównując ze

zbiorem $S$ łatwo dojdziemy do wniosku, że $S$ jest co najmniej tak

samo liczny jak $Q$.

Algorytm jest oczywiście wielomianowy.

Przy dowodzeniu NP-zupełności zacieśnienia ${\mathrm{\Pi }}_r$ danego problemu

$\mathrm{\Pi }$ możemy oczywiście nie korzystać z tego, co dotychczas wiemy o

NP-zupełności problemu. Jednakże warto na ogół zastanowić się, czy

nie przyniesie sukcesu jedna z dwóch poniższych nasuwających się

metod:

1. Wykorzystać znaną redukcję z problemu $Q$ do $\mathrm{\Pi }$, dowodzącą

NP-zupełności problemu $\mathrm{\Pi }$. Warianty tej metody mogą być

następujące:

1. • Redukcja ta wykorzystuje tylko instancje należące do ${\mathrm{\Pi }}_r$.

Wówczas dowód już mamy.

1. • Istnieje NP-zupełny podproblem $Q_r$ problemu $Q$ taki, że

wspomniana redukcja zacieśniona do $Q_r$ przeprowadza instancje

wejściowe w dziedzinę problemu ${\mathrm{\Pi }}_r$

1. • Istniejąca redukcja daje się łatwo przekształcić tak, że do jej

obrazu należą tylko instancje problemu $\mathrm{\Pi }$.

1. Skonstruować redukcję z problemu $\mathrm{\Pi }$ do jego podproblemu ${\mathrm{\Pi }}_r$.

Znanym nam dobrze przykładem zastosowania metody 2 jest dowód

NP-zupełności problemu 3SAT. Inne, trudniejsze przykłady poznamy w

dalszej części tej lekcji.

Jeśli chodzi o pierwszą z metod, to wariant pierwszy tej metody --

możliwość przytoczenia bezpośrednio istniejącej redukcji -- ma

zastosowanie na przykład w dowodzie NP-zupełności pewnego

zacieśnienia problemu komiwojażera. Wymagamy w nim aby odległości w

sieci spełniały warunek trójkąta, przykład ten omawiany jest w

następnym wykładzie.

Drugą z wymienionych możliwości poznamy na przykładzie problemu

zbioru niezależnego. Prostą do sprawdzenia własnością grafów, która

w istotny sposób może ograniczyć trudność problemu, jest maksymalny

dopuszczalny stopień wierzchołka. Wykażemy, że problem INDEPENDENT

SET jest NP-zupełny nawet jeśli ograniczamy się do grafów o stopniu

wierzchołka nie przekraczającym 4. W tej wersji jest on jednym z

ważnych problemów w klasie MAXSNP omawianej w dalszych wykładach.

Twierdzenie

Problem 4INDEPENDENT SET jest NP-zupełny

Dowód

Przyjrzyjmy się znanej redukcji z problemu 3SAT do INDEPENDENT SET -

jest to ta sama redukcja co z 3SAT do NODE COVER omawiana w

poprzednim wykładzie, należy tylko zastąpić wartość generowanego

parametru $k$ przez $m$, liczbę klauzul. Otrzymujemy następującą

równoważność: formuła wejściowa jest spełnialna wtedy i tylko wtedy,

gdy graf zdefiniowany w wyniku redukcji posiada zbiór niezależny o

$m$ wierzchołkach.

TUTAJ PONOWNIE RYSUNEK ZO-5.1.

[width=10cm]{ZO-5-rys-1.jpg}

NP-zupełnym podproblemem problemu 3SAT jest 3OCCUR 3SAT. Zauważmy,

że jeśli formuła na wejściu spełnia ograniczenie, że żaden literał

nie pojawia sie więcej niż 2 razy, to stopień każdego wierzchołka

grafu wygenerowanego przez redukcję nie przekracza 4: krawędzie

trójkąta wnoszą do stopnia wierzchołka 2, przeciwny do danego

literał wnosi co najwyżej 2.

Pozostaje jeszcze niuans związany z tym, że w problemie 3OCCUR 3SAT

istotnie ważne są klauzule o długości mniejszej niż 3 (jeśli

wejściowa formuła jest postaci 3SAT to możemy założyć, że w każdej

klauzuli występują dokładnie 3 różne zmienne i tego problemu nie

ma). Rozwiązanie jest proste: klauzule dwuskładnikowe przekształcamy

w odcinki (pojedyncze krawędzie), natomiast jednoskładnikowe w

punkty (pojedyncze wierzchołki), i tak samo łączymy z innymi

trójkątami, odcinkami i punktami.

Zatem redukcja z problemu 3SAT do INDEPENDENT SET okazała się

również redukcją (prawie) z 3OCCUR 3SAT do 4INDEPENDENT SET.

Bardzo ważnym dla zastosowań jest problem kolorowania. Okazuje sie

on trudny nawet dla bardzo mocnych zawężeń. Jako pierwsze z nich

przeanalizujemy ograniczenie na stopień wierzchołków.

Jeśli to ograniczenie wynosi 2, to graf składa się ze ścieżek i

cykli, i jest łatwo rozstrzygnąć czy potrzebne są 2 kolory czy 3.

Jeśli maksymalny dopuszczalny stopień wynosi 3, to znane jest

twierdzenie mówiące, że taki graf jest trójkolorowalny wtedy i tylko

wtedy gdy nie zawiera kliki rzędu 4 -- warunek ten łatwo sprawdzić w

czasie proporcjonalnym do $n^4$. Dopuszczenie wierzchołków stopnia 4

stanowi przeskok do problemu trudnego.

Twierdzenie

Problem 3COLORING jest NP-zupełny, nawet jeśli zakładamy że jego

dziedzina jest zawężona do grafów o stopniu wierzchołka nie

przekraczającym 4.

Dowód

Stosujemy metodę 2, mianowicie redukujemy problem trójkolorowania

dla dowolnych grafów do tego samego problemu dla grafów o stopniu

wierzchołka nie przekraczającym 4.

Podstawą konstrukcji jest gadżet $G_3$, przedstawiony na sąsiednim

rysunku, pozwalający zastępować wierzchołki o stopniu większym niż 4

odpowiednim podgrafem. Postać takiego podgrafu $G_d$ zastępującego

wierzchołek $v$ o stopniu $deg(v)=d=6$ jest również przedstawiony na

rysunku -- składa się on z $d-2$ kopii gadżetu $G_3$. Własności

grafu $G_d$ są następujące:

[width=10cm]{ZO-6-rys-2.jpg}

• jest trójkolorowalny i nie jest dwukolorowalny
• jego rozmiar jest liniowy w stosunku do $d$
• wszystkie jego wierzchołki mają stopień nie większy niż 4, a

$d$ wierzchołków narożnych (nazywanych dalej zewnętrznymi) ma

stopień 2

• każde trójkolorowanie przypisuje wierzchołkom

narożnym ten sam kolor

Redukcja zatem działa według następującego algorytmu.

{Niech $G$ będzie grafem wejściowym}

{$G^{\prime }:=G$}

while $G^{\prime }$ zawiera wierzchołek $v$ : $deg(v)>4$

{usuń $v$ z $G^{\prime }$}

{dodaj do $G^{\prime }$ nową kopię grafu $G_d$}

{połącz krawędzią każdy wierzchołek zewnętrzny w $G_d$ z innym

spośród dotychczasowych sąsiadów wierzchołka $v$, w dowolnej

kolejności}

endwhile

return{$G^{\prime }$}

Zastąpienie wierzchołka gadżetem nie wprowadza nowych wierzchołków o

stopniu większym niż 4, zatem w grafie wynikowym nie ma takich

wierzchołków.

Zastąpienie w trójkolorowalnym grafie $G$ wierzchołka $v$ o stopniu

$d>4$ przez $G_d$, tak jak opisano powyżej, tworzy graf $G^{\prime }$ również

trójkolorowalny. Mianowicie, kolorowanie zadane w $G$ przenosimy na

$G^{\prime }$ w ten sposób, że kolory wierzchołków w $G-v$ pozostawiamy,

wszystkim wierzchołkom zewnętrznym w $G_d$ dajemy kolor wierzchołka

$v$, pozostałe wierzchołki w $G_d$ kolorujemy tak, aby otrzymać

poprawne trójkolorowanie. Ta ostatnia czynność jest wykonalna dzięki

własnościom gadżetu $G_d$. Zatem, jeśli graf wejściowy jest

trójkolorowalny, to grafy otrzymywane w wyniku kolejnych iteracji

algorytmu redukcji też są trójkolorowalne, a więc graf wynikowy

również.

Podobnie dowodzimy, że istnienie trójkolorowania grafu $G^{\prime }$

implikuje istnienie trójkolorowania grafu $G$.

Dzieki ograniczeniom na rozmiar tworzonego grafu redukcję można

wykonać w pamięci logarytmicznej.

W zastosowaniach bardzo ważna jest inna własność grafów: planarność.

Teoretycznie, grafy planarne są stosunkowo rzadkie. Praktycznie,

mamy z nimi do czynienia bardzo często. Czy obliczeniowa trudność

problemu znika, gdy od rozpatrywanych grafów wymagamy dodatkowo tej

własności?

Oczywiście, zależeć to będzie od problemu. W przypadku problemu

3COLORING ograniczenie sie do grafów planarnych, nawet przy

założeniu, że stopień wierzchołka nie przekracza 4, zachowuje

NP-zupełność problemu. Dowód nie jest łatwy, ale warto spróbować

zrobić go samodzielnie.

Wykaż, że problem 3COLORING jest NP-zupełny, nawet jeśli dziedzina

problemu jest ograniczona do grafów planarnych.

Wskazówka

Zredukuj ten sam problem dla dowolnych grafów.

Wskazówka

Narysuj graf na płaszczyźnie, z przecięciami krawędzi jeśli trzeba.

Krawędzie nie mogą dotykać innych wierzchołków niż ich własne końce,

a więcej niż dwie krawędzie mogą się stykać tylko w wierzchołkach.

Wszystkie przecięcia krawędzi zamień przez odpowiedni gadżet, który

przekazuje informację o kolorze wzdłuż obu krawędzi, na których

przecięciu jest usadowiony.

Rozwiązanie

Konstruujemy redukcję z problemu 3COLORING. Na wejściu mamy zatem

dowolny graf $G$, należy skonstruować planarny graf $G^{\prime }$ taki, że

$G^{\prime }$ jest trójkolorowalny wtedy i tylko wtedy, gdy $G$ jest

trójkolorowalny.

Zanurzamy $G$ na płaszczyźnie w zwykły sposób, spełniający warunki

przedstawione we wskazówce. Posłużymy się gadżetem $H$

przedstawionym na rysunku. Składa sie on z 13 wierzchołków i 24

krawędzi (skonstruowanie tego gadżetu jest rzeczywiście najbardziej

żmudną częścią dowodu), i ma następujące własności:

• każde trójkolorowanie $h$ grafu $H$ spełnia $h(a)=h(b)$ oraz

$h(c)=h(d)$

• $H$ można pokolorować trzema kolorami zarówno tak, że

$h(a)=h(b)=h(c)=h(d)$, jak i tak, że $h(a)=h(b)\ne h(c)=h(d)$

[width=10cm]{ZO-6-rys-3.jpg}

Przekształcenie grafu $G$ w $G^{\prime }$ odbywa się w następujący, opisowo

przedstawiony sposób:

{1. W miejscu każdego przecięcia pary krawędzi rozetnij te

krawędzie i wstaw w to miejsce kopię gadżetu $H$, nakładając

rozcięte końce krawędzi na narożne wierzchołki gadżetu}

{2. Na każdej (oryginalnej) krawędzi $(u,v)$, która przecinała

się z inną, sklej każdą parę sąsiednich gadżetów najbliższymi

wierzchołkami narożnymi}

{3. Dla każdej (oryginalnej) krawędzi, która przecinała się z

inną, dowolny z jej końców sklej z najbliższym wierzchołkiem

najbliższego gadżetu wstawionego na tę krawędź}

return{$G^{\prime }=$ otrzymany graf }

Oczywiście $G^{\prime }$ jest planarny, a jego rozmiar jest wielomianowy w

stosunku do rozmiaru grafu $G$.

Każde trójkolorowanie $h$ grafu $G^{\prime }$, zacieśnione do wierzchołków

grafu $G$, jest trójkolorowaniem $G$. Gdyby tak nie było, to w $G$

istniałaby krawędź $(u,v)$ taka, że $h(u)=h(v)$. Jeśli na tej

krawędzi nie ma gadżetów, to mamy sprzeczność z tym, że $h$ jest

kolorowaniem. Załóżmy zatem, że są na niej gadżety, i załóżmy, że

$u$ należy do gadżetu. Z własności gadżetu mamy, że $h(u)=h(w)$,

gdzie $w$ jest najbliższym dla drugiego końca krawędzi, $v$,

wierzchołkiem ciągu gadżetów na tej krawędzi. Ponieważ $(w,v)$ jest

krawędzią w $G^{\prime }$, więc $h(u)=h(w)\ne h(v)$.

W druga stronę, jeśli $h$ jest trójkolorowaniem w $G$, to $h$ można

rozszerzyć do kolorowania $G^{\prime }$ następująco. Niech $(u,v)$ będzie

krawędzią, i niech $u$ należy do gadżetu. Kolor $u$ powtarzamy dla

wszystkich wierzchołków (narożnych w gadżetach) utworzonych na

krawędzi $(u,v)$. To samo oczywiście będzie wykonane dla krawędzi

przecinających $(u,v)$, ale z własności gadżetu, po takim

pokolorowaniu jego wierzchołków, to kolorowanie można uzupełnić do

poprawnego trójkolorowania.

Problemy liczbowe i silna NP-zupełność

Zajmiemy sie teraz analizą problemów NP-zupełnych, w których

występują liczby. Intuicyjnie, chodzi o takie zagadnienia, w których

mamy nie tylko nazwy obiektów (np. wierzchołków grafu), czy też

liczby stosunkowo małe (np. wielkość żądanej kliki -- nie ma sensu

pytać o klikę rzędu przekraczającego liczbę wierzchołków). Chodzi o

sytuacje w których liczby mogą być dowolnie wielkie w porównaniu do

"reszty" instancji, np. w problemie komiwojażera -- długości

krawędzi grafu, w problemie sumy podzbioru -- wagi elementów.

Dla tego ostatniego problemu napiszmy dość znany algorytm, oparty o

technikę programowania dynamicznego.

Na wejściu dana jest tablica liczb naturalnych $A[n]$ oraz liczba

naturalna $B$. Napisz algorytm o złożoności czasowej $O(nB)$

znajdujący podzbiór elementów tablicy, którego suma liczb wynosi

$B$.

Wskazówka

Dla coraz większego początkowego fragmentu tablicy obliczaj dla

każdego $j<B$, czy istnieje podzbiór tego fragmentu o sumie

elementów równej $B$.

Rozwiązanie

{Niech W[0..n,0..B] będzie tablicą wartości logicznych}

{W[0,*]:=FALSE}

{W[0,0]:=TRUE}

for i:=1 TO n

for j:=0 TO B

{W[i,j]:=W[i-1,j]}

if j-A[i]>=0

{W[i,j]:=W[i-1,j] OR W[i-1,j-A[i]]}

endif

endfor

endfor

if W[n,b] returnTAK else returnNIE

endif

Tylko pozornie złożoność tego rozwiązania problemu SUBSET SUM jest

wielomianowa. Złożność, jak dobrze wiemy, jest funkcją rozmiaru

danych, czyli długości ich zapisu. Przy czym zakładamy "rozsądne"

kodowanie instancji, w szczególności wymagamy, aby liczby były

kodowane binarnie. Liczba $B$ w problemie SUBSET SUM jest zapisana

na $\lfloor \log B\rfloor +1$ bitach, i w stosunku do tej wielkości

funkcja $nB$ nie jest wielomianowa, lecz wykładnicza. Jeżeli

złożoność algorytmu jest wielomianowa od rozmiaru danych i wielkości

największej liczby w instancji to mówimy że jest to algorytm o

złożoności pseudowielomianowej.

Zatem nie ma tutaj ani paradoksu, ani tym bardziej odkrycia, że

$P=NP$. Z praktycznego punktu widzenia można jednak dostrzec zalety

takiego algorytmu. Jeśli liczby w instancji nie są wielkie, to takie

rozwiązanie, mimo że niewielomianowe, może być bardzo efektywne.

Naturalne więc staje sie pytanie, czy tego typu sytuacja dotyczy

wszystkich problemów NP-zupełnych, i jak ją można formalnie opisać.

Zauważmy, że na przykład w redukcji z problemu 3SAT do CLIQUE liczby

generowane przez funkcje redukcji mają wielkość wielomianową w

stosunku do rozmiaru formuły. Podobnie jak dla dowodu NP-zupełności

trójdzielnego skojarzenia czy kolorowania. Również w redukcji z

problemu cyklu Hamiltona do komiwojażera wagi krawędzi w generowanym

grafie są ograniczone wielomianowo (faktycznie, przez stałą 2).

Przeciwna sytuacja zachodzi w przypadku redukcji z EXACT COVER BY

3SETS do SUBSET SUM. Generowane przez redukcję liczby są zapisywane

na wielomianowej liczbie bitów, ich wartości są wykładnicze, i to

decyduje o trudności problemu SUBSET SUM. Ta cecha przenosi się na

problem plecakowy oraz problem podziału. Aczkolwiek też NP-zupełne,

te problemy wydają się nieco łatwiejsze niż wcześniej omawiane

problemy grafowe.

Formalizacja pojęcia algorytmu psedowielomianowego w modelu obliczeń

wymaga dodatkowych pojęć. Bez nich instancje wejściowe są po prostu

ciągami bitów, nie posiadającymi struktury! Rozważanie wielkości

liczb w instancji możliwe jest tylko poprzez "dekodowanie" słowa

wejściowego (ciągu bitów), czyli interpretację w terminach problemu

naturalnego. Wprowadźmy zatem potrzebne definicje.

Niech $L$ będzie językiem nad pewnym alfabetem $\mathrm{\Sigma }$. Załóżmy, że

NUM $:{\mathrm{\Sigma }}^{*}\to Z^{+}$ jest funkcją obliczalną

w czasie wielomianowym, i $|x|\le$ NUM $(x)\le 2^{|x|}$, dla każdego słowa $x\in {\mathrm{\Sigma }}^{*}$. Intuicyjnie: funkcja NUM

definiuje wartość największej liczby w instancji $x$. Jeśli $q(n)$

wielomianem, to oznaczmy $L_q=\{x\in L:$ NUM $(x)\le q(n)\}$.

Definicja

Przy oznaczeniach jak powyżej, mówimy że maszyna Turinga działa w

czasie pseudowielomianowym, jeśli dla każdego słowa wejściowego $x$

liczba wykonywanych kroków nie przekracza $p($ NUM $(x))$,

dla pewnego wielomianu $p(n)$.

Język $L$ jest silnie NP-zupełny, jeśli istnieje wielomian $q(n)$

taki, że $L_q$ jest NP-zupełny.

Język (problem) $L$ jest nieliczbowy, jeśli istnieje wielomian

$r(n)$ taki, że dla każdego słowa wejściowego $x$,

NUM $(x)\le r(|x|)$.

Powyższe rozważania mają sens (i zastosowanie praktyczne) tylko w

przypadku właściwego doboru funkcji NUM, mającego odpowiednik w

naturalnej definicji problemu. Na ogół przyjmuje się, że jest to

największa liczba występująca w naturalnej, "rozsądnej" definicji

problemu.

Podaj sensowną definicję funkcji NUM dla problemu SUBSET SUM, dla

której algorytm rozwiązujący poprzednie ćwiczenie jest

pseudowielomianowy.

Rozwiązanie

NUM $(x)=$ max $\{n,B\}$

Z rozważanych dotychczas problemów, nieliczbowe są na

przykład:

• SAT i jego warianty, SET COVERING
• NODE COVER, CLIQUE, HAMILTONIAN CYCLE, COLORING (zauważmy, że

parametr instancji podający rozmiar żądanego pokrycia

wierzchołkowego możemy ograniczyć od góry przez moc zbioru

wierzchołków grafu, podobnie dla wielu innych problemów grafowych)

Z kolei, niewielomianowej (w stosunku do rozmiaru instancji)

wielkości liczby moga pojawiać się w problemach takich jak:

• TRAVELING SALESMAN
• SEQUENCING WITHIN INTERVALS
• SUBSET SUM, PARTITION, KNAPSACK

Łatwo spostrzec, że każdy NP-zupełny problem nieliczbowy jest z

definicji silnie NP-zupelny. Zatem pojęcie to jest istotne dla

problemów zawierających dowolnie wielkie liczby. Zastosowanie

NP-zupełności w analizie złożoności obliczeniowej takich problemów

opiera się na następującym praktycznie bardzo ważnym fakcie:

Twierdzenie

Jeśli P $\ne$ NP , a $\mathrm{\Pi }$ jest problemem

silnie NP-zupełnym, to nie istnieje algorytm pseudowielomianowy dla

$\mathrm{\Pi }$.

Udowodnij powyższe twierdzenie.

Rozwiązanie

${\mathrm{\Pi }}_q$ jest NP-zupełny i nieliczbowy. Każdy algorytm

pseudowielomianowy dla $\mathrm{\Pi }$ staje sie wielomianowy dla ${\mathrm{\Pi }}_q$.

Podsumowując, udowodnienie, że dany problem jest silnie NP-zupełny

praktycznie wyklucza jedną z potencjalnych ścieżek szukania

sensownego rozwiązania, mianowicie algorytmy pseudowielomianowe.

Zatem ma duże znaczenie praktyczne. Przyjrzymy się jeszcze kilku

przykładom.

Wykaż, że problem komiwojażera jest silnie NP-zupełny.

Rozwiązanie

Należy wskazać podproblem powstający przez ograniczenie wielomianowe

na wielkość występujących w nim liczb, który jest NP-zupełny.

Wystarczy zauważyć, że wagi krawędzi i ograniczenie górne na długośc

ścieżki (są to jedyne parametry liczbowe w problemie) mogą być

ograniczone przez $n$. Klasyczna transformacja z HAMILTONIAN CYCLE

wykorzystuje tylko takie instancje problemu komiwojażera, zatem te

instancje stanowią nieliczbowy NP-zupełny podproblem problemu

komiwojażera.

Jednym z częściej stosowanych w dowodach NP-zupełności problemów

jest następujący problem trójpodziału:

Problem 3PARTITION

Wejście: Liczby $B,k\in Z^{+}$ oraz zbiór (być może z

powtórzeniami) $S=\{a_1,\dots ,a_{3m}\},m>0$, liczb całkowitych takich, że $B/4<a_i<B/2$, dla każdego $i$, oraz $\sum _{i=1}^{i=3m}{a}_i=mB.$

Wyjście: TAK, jeśli istnieje podział $S$ na $m$ podzbiorów

takich, że suma liczb w każdym podzbiorze równa jest 1, NIE w

przeciwnym

przypadku.

Pomijamy dość skomplikowany i długi dowód faktu, że 3PARTITION jest

silnie NP-zupełny. Zanim wykorzystamy ten problem, zauważmy jeszcze

jedna ciekawą cechę problemów silnie NP-zupełnych. Mianowicie, jeśli

instancje takiego problemu $\mathrm{\Pi }$ (zdefiniowane w naturalny sposób)

zakodujemy zapisując liczby unarnie, to problem (formalnie:

jezyk $L_u(\mathrm{\Pi })$ odpowiadający mu przy takim kodowaniu) pozostaje

nadal NP-zupełny!

Aby sie o tym przekonać wystarczy rozważyć oba języki dla tego

problemu powstałe przy różnych kodowaniach. Redukcja z języka

$L_b(\mathrm{\Pi })$, w którym kodowanie jest binarne (jest silnie

NP-zupełny), do języka $L_u(\mathrm{\Pi })$, polegająca na zmianie zapisu z

binarnego na unarny, jest redukcją logarytmiczną (długość zapisu

rośnie wielomianowo), zatem $L_u(\mathrm{\Pi })$ jest NP-zupełny.

Wykorzystamy tę własnośc w dowodzie NP-zupełności jeszcze jednego

zacieśnienia znanego nam już problemu NP-zupełnego. Chodzi o

SUBGRAPH ISOMORPHISM, w którym dla zadanych grafów $G_1,G_2$

pytamy, czy $G_1$ zawiera podgraf izomorficzny z $G_2$. Interesują

nas zacieśnienia polegające na zakazie występowania cykli w jednym

lub obu grafach (czyli grafy będące lasami, a w szczególnych

przypadkach - drzewami).

Jeśli tylko o $G_2$ zakładamy, że jest drzewem, to szczególnym

przypadkiem (czyli jeszcze silniejszym zawężeniem) jest wymaganie,

by $G_2$ był ścieżką. Problem staje się równoważny HAMILTONIAN PATH,

a więc jest NP-zupełny.

Jesli o $G_1$ założymy, że jest drzewem, to interesujące staje się

narzucenie $G_2$, by był drzewem lub lasem. Problem izomorfizmu

poddrzewa jest wielomianowy, algorytm jest nietrywialny -- nieco

łatwiejszy jest problem testowania izomorficzności drzew. Co się

dzieje, gdy $G_2$ może byc lasem?

Twierdzenie

Problem SUBGRAPH ISOMORPHISM, w którym dodatkowo zakładamy, że $G_1$

jest drzewem, a $G_2$ lasem, jest NP-zupełny.

Dowód

Skonstruujemy redukcję z problemu 3PARTITION. Na wejściu mamy liczby

$B,k\in Z^{+}$ oraz ciąg $a_1,\dots ,a_{3m}$ liczb całkowitych takich,

że $B/4<a_i<B/2$, dla każdego $i$, oraz $\sum _{i=1}^{i=3m}{a}_i=mB.$

Drzewo $G_1$ zbudowane jest z $m$ rozłącznych ścieżek, każda ma

długość $B$ (czyli ma $B+1$ wierzchołków), a pierwszy wierzchołek

każdej ścieżki jest połączony krawędzią z korzeniem $r$.

Las $G_2$ składa się z gwiazdy $S$ o $m$ ramionach oraz $3m$

rozłącznych ścieżek, kolejne ścieżki zawierają odpowiednio

$a_1,a_2,\dots ,a_{3m}$ wierzchołków.

[width=10cm]{ZO-6-rys-4.jpg}

Ponieważ stopień korzenia gwiazdy w $G_2$ wynosi co najmniej 3, więc

każde włożenie $G_2$ w $G_1$ musi utożsamić korzeń gwiazdy z

korzeniem $r$ i wykorzystać początkowe węzły ścieżek w $G_1$. Zatem

ścieżki $P_1,\dots ,P_{3m}$ można zanurzyć w ścieżki drzewa wtedy i

tylko wtedy, gdy można je pogrupować po 3, tak aby suma liczby

wierzchołków w każdej grupie była równa $B$, a to odpowiada żądanemu

trójpodziałowi.

I teraz ciekawa rzecz: tak zdefiniowana redukcja nie jest redukcją

logarytmiczną! Powód: działa w czasie wykładniczym, bo dla liczby

$a_i$ generuje na wyjściu ścieżkę długości $a_i$, co musi zająć czas

wykładniczy od długości zapisu lizby $a_i$, czyli od $\log a_i$. I

tu przychodzi nam z pomocą silna NP-zupełność problemu 3PARTITION.

Mianowicie zakładamy, że problem ten został zakodowany unarnie. W

tej sytuacji rzeczywiście nasz dowód staje sie poprawny.

Poznaliśmy zatem ciekawy przypadek dowodzenie NP-zupełności problemu

nieliczbowego przez redukcję z silnie NP-zupełnego problemu

liczbowego, jakim jest problem trójpodziału.

Ćwiczenia dodatkowe

Wykaż, że NP-zupełna jest wersja NAE3SAT problemu 3SAT, w której

pytamy o istnienie wartościowania, dla którego w każdej klauzuli

występuje zarówno prawda jak i fałsz. Zakładamy, że wejściowe

klauzule zawierają zawsze 3 literały.

Zauważ, że nie używamy tutaj pojęcia "podproblem", gdyż dziedzina

jest wprawdzie taka sama (ciąg klauzul co najwyżej

trójskładnikowych), ale pytanie jest nieco inne.

Wskazówka

Problem wydaje się dość trudny, ale taki nie jest, jeśli wpadnie się

na trop. To co może na poczatku utrudniać, to fakt, że zaprzeczenie

wartościowania spełniającego formułe w sensie NAESAT również spełnia

te formułę. Zatem potrzebna jest nowa zmienna, która będzie

reprezentowała prawdę lub fałsz, i wartości innych zmiennych będa

obliczane względem tej nowej, wyróżnionej.

Po drodze otrzymasz NP-zupełny problem NAE4SAT. Z nim zrób to samo

co w redukcji z SAT do 3SAT.

Rozwiązanie

Redukuj 3SAT, zmieniając każdą klauzulę $(a\vee b\vee c)$ na $(a\vee b\vee c\vee z)$, zawsze z tą samą zmienną $z$. Jeśli istnieje

wartościowanie spełniające formułę wejściowa, to kładąc $z=0$

otrzymujemy wartościowanie spełniające formułę wynikową zgodnie z

wymaganiami NAESAT. W druga stronę, jeśli wartościowanie spełnia

formułę wynikową, to:

• jeśli $z=0$, to w każdej klauzuli jest literał o wartości 1, i

formuła wejściowa jest spełniona

• jeśli $z=1$, to negujemy wartościowanie, zgodnie z regułą NAESAT ono

również spełnia formułę wynikową, ale teraz mamy $z=0$ i stosujemy

poprzedni punkt

Pozostaje zauważyć, że przekształcenie stosowane w redukcji SAT do

3SAT:

$(a\vee b\vee c\vee d)⟹(a\vee b\vee u)\wedge (\mathrm{\neg }u\vee c\vee d)$

gdzie każda zmienna $u$ jest unikalna dla kolejnych klauzul,

zachowuje własność wartościowania NAESAT.

Wykaż, że problem pakowania jest silnie NP-zupełny.

Problem BIN PACKING

Wejście: zbiór $n$ przedmiotów o wagach wymiernych $w_1,w_2,\dots ,w_n\in (0,1]$, oraz liczba naturalna $k$

Wyjście: TAK, jeśli wszystkie te przedmioty mozna upakować w $k$ pojemnikach, przy czym suma wag w każdym pojemniku nie może przekraczać 1, w przeciwnym przypadku NIE

Rozwiązanie

Nietrudno spostrzec, że 3PARTITION, po przeskalowaniu wag elementów,

jest podproblemem problemu pakowania. Skalowanie to pozwala również

zdefiniować odpowiedni wielomian ograniczający wagi elementów

(dokładniej, licznik i mianownik każdej wagi), na podstawie

wielomianu istniejącego dla problemu trójpodziału.