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

Wstęp

Zacieśnienie problemu polegające na nałożeniu dodatkowych warunków, które muszą być spełnione przez instancję, może zmniejszyć złożoność problemu. W tym wykładzie 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ść

W poprzednim wykładzie 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.

Rysunek 6.1.

Dowód

Każdą alternatywę $C_{j}=x_{1}\vee x_{2}$ można traktować jako implikację $\neg x_{1}\Rightarrow x_{2}$. Rozważmy zatem graf skierowany $G(\phi )$ dla wejściowej formuły $\phi$ zbudowany następująco:

• dla każdej zmiennej $x_{i}$ wstępującej w formule tworzymy dwa wierzchołki: $x_{i}$ oraz $\neg$ $x_{i}$,
• dla każdej alternatywy $C_{j}=u\vee v$ tworzymy dwie krawędzie: $(\neg u,v)$ oraz $(\neg v,u)$.

W ten sposób krawędzie grafu opisują implikacje logiczne zawarte w formule $\phi$: jeśli $C_{j}=u\vee v$ występuje w formule, i pewne wartościowanie kładzie $u=0$ (czyli $\neg u=1$), to w tym wartościowaniu zachodzi $v=1$. Zatem jeśli początek krawędzi grafu $G(\phi )$ ma wartość 1, to koniec krawędzi również. Zauważmy, że symetria w grafie, polegająca na tym, że istnieją obie krawędzie: $(\neg u,v)$ oraz $(\neg v,u)$, odpowiada po prostu kontrapozycji w każdej implikacji.

Rysunek 6.1 przedstawia $G(\phi )$ dla przykładowej formuły:

$\phi =(\neg x_{1}\vee \neg x_{2})\wedge (x_{1}\vee x_{4})\wedge (x_{2}\vee x_{3})\wedge (x_{2}\vee \neg x_{3})\wedge (\neg x_{2}\vee \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 $\neg x_{2}$, co oznacza że $\neg x_{2}$ też musi mieć wartość 1, zatem nie istnieje wartościowanie spełniające formułę $\phi$, w którym $x_{2}=1$. Ale jeśli położymy $x_{2}=0$, to, ponieważ istnieje również ścieżka z $\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(\phi )$ dla pewnej zmiennej Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x_i} wierzchołki Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x_i} oraz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x_i} należą do pewnego cyklu, to formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \phi} nie jest spełnialna. Okazuje się, że prawdziwa jest również implikacja odwrotna. Wykażemy mianowicie, że jeśli dla każdej zmiennej Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x_i} wierzchołki Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x_i} oraz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x_i} nie leżą na wspólnym cyklu, to istnieje wartościowanie spełniające Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \phi} .

Zacznijmy od dowolnego wierzchołka Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle v} takiego, że nie istnieje ścieżka z Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle v} do Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg v} . Z założenia wynika, że dla każdej zmiennej Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x_i} co najmniej jeden z wierzchołków Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x_i} oraz Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \neg} Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 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 $\neg v$, posuwając się wstecz (czyli: jedynkę propagujemy w przó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 $\neg w$ są osiągalne z $v$, co pociągałoby istnienie ścieżki z $v$ do $\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, że kolejne powtórzenia procedury sa poprawne i 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 musiało być 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ą problemu 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ż $\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 $\phi$ 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 $\phi$ jest spełnialna, NIE, w przeciwnym przypadku.

Ćwiczenie 2.1

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

Wskazówka

Wystąpienia zmiennej, która pojawia się zbyt często, 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 $\phi$. Kolejne wystąpienia $x$ zastępujemy nowymi zmiennymi $y_{1},\ldots ,y_{k}$ i dodajemy ciąg implikacji $y_{1}\Rightarrow y_{2}\Rightarrow \ldots \Rightarrow y_{k}\Rightarrow y_{1}$, czyli alternatywy $(\neg$ $y_{1}\vee y_{2}),(\neg y_{2}\vee y_{3}),\ldots ,(\neg y_{k-1}\vee y_{k}),(\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.

Ćwiczenie 2.2

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|\geq |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ł, niebędący negacją zmiennej (literał pozytywny). Taką klauzulę, jeśli zawiera literał pozytywny, wygodnie jest traktować jako implikację, np. $(\neg x_{1}\vee \neg x_{2}\vee x_{3}\vee \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 $\phi$ 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=\emptyset$. 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 \ldots \wedge x_{k})\Rightarrow z)$, która jest niespełniona, a więc wartości zmiennych $x_{1},\ldots ,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. $(\neg x_{1}\wedge \ldots \wedge \neg x_{k})$, i wszystkie te zmienne mają 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 łatwa do zrealizowania 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

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 $\Pi _{r}$ danego problemu $\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 $\Pi$ dowodzącą NP-zupełności problemu $\Pi$. Warianty tej metody mogą być następujące:
   • Redukcja ta wykorzystuje tylko instancje należące do $\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 $\Pi _{r}$
   • Istniejąca redukcja daje się łatwo przekształcić tak, że do jej obrazu należą tylko instancje problemu $\Pi$.
2. Skonstruować redukcję z problemu $\Pi$ do jego podproblemu $\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 tego wykładu.

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

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 się 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.

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 nieprzekraczają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 nieprzekraczają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.

Niech $G$ będzie grafem wejściowym 
$G':=G$ 
while $G'$ zawiera wierzchołek $v$ : $deg(v)>4$ do
  usuń $v$ z $G'$ 
  dodaj do $G'$ 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
end while
return  $G'$ 

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'$ również trójkolorowalny. Mianowicie, kolorowanie zadane w $G$ przenosimy na $G'$ 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'$ 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 się 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

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

Rysunek 6.4.

Konstruujemy redukcję z problemu 3COLORING. Na wejściu mamy zatem dowolny graf $G$; należy skonstruować planarny graf $G'$ taki, że $G'$ 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 6.4. Składa się 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)\neq h(c)=h(d)$.

Przekształcenie grafu $G$ w $G'$ 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ź.
4. return  $G'=$ otrzymany graf  

Oczywiście $G'$ jest planarny, a jego rozmiar jest wielomianowy w stosunku do rozmiaru grafu $G$.

Każde trójkolorowanie $h$ grafu $G'$, 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, iż $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'$, więc $h(u)=h(w)\neq h(v)$.

W druga stronę, jeśli $h$ jest trójkolorowaniem w $G$, to $h$ można rozszerzyć do kolorowania $G'$ 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 się 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

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 do
  for j:=0 TO B do
    W[i,j]:=W[i-1,j] 
    if j-A[i]>=0 then
      W[i,j]:=W[i-1,j] OR W[i-1,j-A[i]] 
    end if
  end for
end for
if W[n,b] then
  return  TAK  
else 
  return  NIE 
end if

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, nieposiadają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 $\Sigma$. Załóżmy, że NUM $:\Sigma ^{*}\rightarrow Z^{+}$ jest funkcją obliczalną w czasie wielomianowym, i $|x|\leq {\mbox{ NUM }}(x)\leq 2^{|x|}$, dla każdego słowa $x\in \Sigma ^{*}$. Intuicyjnie: funkcja NUM definiuje wartość największej liczby w instancji $x$. Jeśli $q(n)$ wielomianem, to oznaczmy $L_{q}=\{x\in L:{\mbox{ NUM }}(x)\leq 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)\leq 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

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-zupełny. 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 $\neq$ NP , a $\Pi$ jest problemem silnie NP-zupełnym, to nie istnieje algorytm pseudowielomianowy dla $\Pi$.

Ćwiczenie 3.3

Udowodnij powyższe twierdzenie.

Rozwiązanie

$\Pi _{q}$ jest NP-zupełny i nieliczbowy. Każdy algorytm pseudowielomianowy dla $\Pi$ staje się wielomianowy dla $\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.

Ćwiczenie 3.4

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ść ś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},\ldots ,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 $\Pi$ (zdefiniowane w naturalny sposób) zakodujemy, zapisując liczby unarnie, to problem (formalnie: jezyk $L_{u}(\Pi )$ odpowiadający mu przy takim kodowaniu) pozostaje nadal NP-zupełny!

Aby się o tym przekonać wystarczy rozważyć oba języki dla tego problemu powstałe przy różnych kodowaniach. Redukcja z języka $L_{b}(\Pi )$, w którym kodowanie jest binarne (jest silnie NP-zupełny), do języka $L_{u}(\Pi )$, polegająca na zmianie zapisu z binarnego na unarny, jest redukcją logarytmiczną (długość zapisu rośnie wielomianowo), zatem $L_{u}(\Pi )$ jest NP-zupełny.

Wykorzystamy tę własność 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.

Jeśli 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 być 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.

Rysunek 6.5.

Dowód

Skonstruujemy redukcję z problemu 3PARTITION. Na wejściu mamy liczby $B,k\in Z^{+}$ oraz ciąg $a_{1},\ldots ,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},\ldots ,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},\ldots ,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 liczby $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 się 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

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 początku utrudniać, to fakt, że zaprzeczenie wartościowania spełniającego formułę w sensie NAESAT również spełnia tę formułę. Zatem potrzebna jest nowa zmienna, która będzie reprezentowała prawdę lub fałsz i wartości innych zmiennych będą 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)\,\,\Longrightarrow \,\,(a\vee b\vee u)\wedge (\neg u\vee c\vee d)$

gdzie każda zmienna $u$ jest unikalna dla kolejnych klauzul, zachowuje własność wartościowania NAESAT.

Ć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},\ldots ,w_{n}\in (0,1]$ oraz liczba naturalna $k$.
Wyjście: TAK, jeśli wszystkie te przedmioty można 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.