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 2.1

Problem 2SAT jest rozwiązywalny w czasie wielomianowym.

<flash>file=ZO-6-1.swf|width=350|height=350</flash>

<div.thumbcaption>Rysunek 6.1.

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 6.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)$

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ść 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.

Ćwiczenie 2.1

{{{3}}}

Ćwiczenie 2.2

{{{3}}}

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 2.2

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 2.3

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.

Ćwiczenie 2.3

{{{3}}}

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:
   • Redukcja ta wykorzystuje tylko instancje należące do ${\mathrm{\Pi }}_r$. Wówczas dowód już mamy.
   • 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$
   • Istniejąca redukcja daje się łatwo przekształcić tak, że do jej obrazu należą tylko instancje problemu $\mathrm{\Pi }$.
2. 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 2.4

Problem 4INDEPENDENT SET jest NP-zupełny

<flash>file=ZO-5-1.swf|width=350|height=250</flash>

<div.thumbcaption>Rysunek 6.2.

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. (porównaj: rysunek 6.2.)

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.

<flash>file=ZO-6-2.swf|width=300|height=300</flash>

<div.thumbcaption>Rysunek 6.3.

Twierdzenie 2.5

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 (porównaj rysunek 6.3):

• 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.

Algorytm

---

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.

Ćwiczenie 2.4

{{{3}}}

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.

Ćwiczenie 3.1

{{{3}}}

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 3.1

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.

Ćwiczenie 3.2

{{{3}}}

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 3.2

Jeśli P $\ne$ NP , a $\mathrm{\Pi }$ jest problemem silnie NP-zupełnym, to nie istnieje algorytm pseudowielomianowy dla $\mathrm{\Pi }$.

Ćwiczenie 3.3

{{{3}}}

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.

Ćwiczenie 3.4

{{{3}}}

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 3.3

Problem SUBGRAPH ISOMORPHISM, w którym dodatkowo zakładamy, że $G_1$ jest drzewem, a $G_2$ lasem, jest NP-zupełny.

<flash>file=ZO-6-4.swf|width=350|height=350</flash>

<div.thumbcaption>Rysunek 6.5.

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 (porównaj rysunek 6.5.).

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

Ćwiczenie 4.1

{{{3}}}

Ćwiczenie 4.2

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.