Złożoność obliczeniowa/Wykład 5: Problemy NP-zupełne

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Wstęp

Jak czytelnikowi wiadomo, w aktualnym stanie wiedzy NP-zupełność jest podstawowym narzędziem do badania probelu algorytmicznego pod kątem jego trudności obliczeniowej. Na tym wykładzie dla wielu znanych klasycznych problemów z teorii grafów, kombinatoryki, logiki i innych podajemy definicje ich decyzyjnych wersji i wykazujemy ich NP-zupełność. Z problematyką tą spotkaliśmy się już na kursie Algorytmy i struktury danych. Tutaj rozbudowujemy te wiadomości, czynimy je bardziej formalnymi, posługując się modelem maszyny Turinga i redukcją logarytmiczną. Na przedstawionych przykładach omawiamy również techniki dowodzenia NP-zupełności. Następny wykład pokazuje wykorzystanie tych technik do analizy złożoności problemu i jego zawężeń.

O problemie SAT

Aby wykazać, że dany problem z klasy NP jest NP-zupełny, zgodnie z własnościami redukcji logarytmicznej (przechodniość) wystarcza pokazać, dla dowolnego problemu , że redukuje się do . Innymi słowy, proces dowodzenia że dany problem jest w NPC składa sie z nastepujących kroków:

  • dowieść że należy do NP
  • wybrać znany problem NP-zupełny i skonstruować redukcję z do .

Przypomnijemy, że redukcja z problemu A do B dowodzi, że B jest niełatwiejszy niż A. Zatem dla konstrukcji takiej redukcji łatwiej jest, gdy (są to rozważania czysto intuicyjne):

  • problem A nie jest skomplikowany, tzn. instancje tego problemu wykazują pewną regularność, łatwą do "opisu" lub "zmierzenia"
  • problem B dopuszcza konstrukcje różnorodnych instancji, jest "bogaty strukturalnie"

Stąd dla wypracowania sobie "warsztatu" dla konstruowania dowodów NP-zupełności warto rozpocząć od dowiedzenia tej własności dla kilku nieskomplikowanych (pod wzgledem opisu struktury) problemów. W rzeczywistości, w literaturze dotyczącej tych zagadnień, można wyodrębnić niewielką grupę klasycznych w tym sensie problemów, które najczęściej wystepują jako lewa strona redukcji w dowodach NP-zupełnosci. Poniżej definiujemy lub przypominamy grupe takich problemów, dość różnorodnego pochodzenia i zastosowania i dowodzimy ich NP-zupełności.

Najpierw 3SAT

Zaczynamy od sytuacji, w której jedynym znanym problemem NP-zupełnym (a więc możliwą lewą stroną redukcji) jest problem SAT. Jest on dość niewygodny jako problem źródłowy, redukcja z SAT do innego problemu na ogół wymaga skomplikowanego opisu. Okazuje się (wykazał to już Cook w swojej fundamentalnej pracy o NP-zupełności), że podproblem problemu SAT, w którym wymagamy, aby każda klauzula zawierała nie więcej niż 3 literały, jest sam w sobie NP-zupełny, a dowód tego faktu jest dość łatwy.

Twierdzenie 2.1

Problem 3SAT jest NP-zupełny.

Dowód

Problem 3SAT, jako podproblem problemu w klasie NP, sam należy do NP, zatem pierwsza część dowodu jest za nami.

Konstruujemy redukcję z problemu SAT do 3SAT. Na wejściu mamy formułe nad zmiennymi . Każdą z klauzul przekształcamy osobno. Bez straty ogólności załóżmy, że , gdzie są parami różne. Jeśli to kładziemy .

Niech . Dodajemy nowych zmiennych , i zastepujemy przez



Nietrudno spostrzec, że jeśli jest spełniona przez pewne wartościowanie zmiennych , to da się tak dobrać wartości dla zmiennych , aby spełnione były wszystkie klauzule w . Na odwrót, jeśli jest spełniona dla pewnego wartościowania zmiennych , to łatwo wydedukować, że dla pewnego . Mianowicie, jeśli , to z pierwszej klauzuli w wynika że . Ale wtedy z drugiej klauzuli mamy lub . W pierwszym przypadku rozumowanie jest zakończone, w drugim przenosimy rozumowanie na trzecią klauzulę i tak dalej.

Zatem, po przekształceniu kolejno wszystkich alternatyw powstaje równoważna formuła o co najwyżej trójskładnikowych alternatywach. Pozostaje wykazać, że przekształcenie to realizowalne jest w pamięci logarytmicznej. Zauważmy jednak, że aby wypisać formułę wynikową, MT potrzebuje pamięć roboczą tylko na licznik bieżącej alternatywy oraz licznik wygenerowanych do tej pory nowych zmiennych.

End of proof.gif
Uwaga 2.1

Zapewne zauważyłaś(-łeś), że w wielu podręcznikach do algorytmiki również mówi się o NP-zupełności. Na ogół korzysta się wtedy z redukcji wielomianowej. Złożoność czasowa jest łatwiejsza do analizy w przypadku modelu obliczeń takiego jak (uproszczony) język programowania wysokiego poziomu. Analiza złożoności pamięciowej (i to tylko z uwzględnieniem pamięci roboczej) może być trudniejsza.

Redukcja logarytmiczna jest bardziej uniwersalna i dlatego stosujemy ją w teorii złożoności.

Uwaga 2.2

W literaturze przyjmuje sie również nieco inną definicję problemu 3SAT, w której zakłada sie dodatkowo, że w każdej klauzuli występują dokładnie 3 parami różne literały. Dowód NP-zupełności tej wersji otrzymujemy przez uzupełnienie dowodu powyższego w następujący sposób:

Załóżmy że . Wprowadzamy nową zmienną i kładziemy . Jeśli istnieje wartościowanie spełniające formułę , to w tym wartościowaniu formuła powstała z przez zastąpienie klauzuli formułą jest również spełniona. I na odwrót, jeśli pewne wartościowanie spełnia formułę , to aby było prawdziwe lub musi mieć wartość 1, a zatem to samo wartościowanie (bez zmiennej ) spełnia formułę .

Analogicznie, jesli składa się tylko z jednego literału, to przekształcamy go w koniunkcję czterech trójskładnikowych klauzul, z dodanymi dwiema nowymi zmiennymi.

Z tego spostrzeżenia będziemy korzystać w następnych dowodach NP-zupełności.

Odnotujmy w tym miejscu, że dalsze zawężenie problemu polegające na dopuszczeniu klauzul o co najwyżej dwóch literałach, 2SAT, jest problemem obliczeniowo łatwym. Dowód tego faktu odkładamy do następnej lekcji.

MAXSAT

Warto wspomnieć o innych NP-zupełnych wersjach problemu spełnialnosci. Na przykład, możemy zapytać o istnienie wartościowania spełniającego co najmniej zadaną liczbe klauzul (a niekoniecznie wszystkie). Problem ten nosi nazwę MAXSAT, i jest ogólniejszy niż SAT (a zatem jest również w NPC). Jego trudność przejawia sie również w tym, że zawężenie do klauzul długości dwa w przeciwieństwie do SAT, pozostawia ten problem trudnym.

Twierdzenie 2.2 [MAX2SAT]

Problem MAX2SAT jest NP-zupełny.

Dowód

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

Tych 10 klauzul ma następujące własności:

  1. Jeśli , to niezależnie od wartości zmiennej co najwyżej 6 klauzul jest spełnionych.
  2. Jeśli któryś z literałów , lub jest równy 1, to

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

Pozostaje zdefiniować żądaną liczbę spełnionych klauzul w formule wynikowej na . Z wymienionych własności wynika, że formuła wynikowa posiada wartościowanie spełniające dokładnie alternatyw wtedy i tylko wtedy gdy formuła wejściowa jest spełnialna.

Maszyna Turinga realizująca redukcję potrzebuje pamieci roboczej jedynie na liczniki, zatem działa w pamięci logarytmicznej.

End of proof.gif

NP-zupełne problemy grafowe

Pokrycie wierzchołkowe

Pierwszym z serii problemów grafowych, dla których udowodnimy NP-zupełność, jest problem pokrycia wierzchołkowego. Dla grafu nieskierowanego mówimy, że podzbiór jest pokryciem wierzchołkowym, jeśli każda krawędź w G ma co najmniej jeden z końców w zbiorze .

Problem [NODE COVER]

Wejście: Graf nieskierowany , liczba całkowita

Wyjście: TAK jeśli G ma pokrycie wierzchołkowe o liczności k, NIE w przeciwnym przypadku.

Twierdzenie 3.1 [Problem NODE COVER]

Problem NODE COVER jest NP-zupełny.

Redukcja 3SAT do NODE COVER

Dowód

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

Redukujemy problem 3SAT do NODE COVER. Na wejściu mamy formułę , i zgodnie z uwagą poczyniona przy dowodzie NP-zupełności 3SAT zakładamy, że każda alternatywa zawiera dokładnie 3 różne literały. Konstruujemy graf następujący: każde wystąpienie literału jest wierzchołkiem grafu, wystąpienia wewnątrz jednej klauzuli tworzą trójkąt. Ponadto, dla każdej pary literałów przeciwnych wystepujących w różnych klauzulach odpowiadające im wierzchołki łączymy krawędzią. Na koniec, kładziemy (patrz rysunek Redukcja 3SAT do NODE COVER).

Teraz należy wykazać, że formuła wejsciowa jest spełnialna wtedy i tylko wtedy, gdy wygenerowany graf ma pokrycie wierzchołkowe o liczności . Z ograniczenia na wielkość pokrycia wynika, że z każdego trójkąta do pokrycia muszą być wybrane dokładnie dwa wierzchołki. Jeśli formuła jest spełnialna, to w każdym trójkącie można wyróżnić jeden wierzchołek odpowiadający literałowi równemu 1. Do pokrycia wybieramy pozostałe dwa wierzchołki. Pokrywają one wszystkie krawędzie trójkątów oraz wychodzące z tych wierzchołków krawędzie między trójkątami. Każda pozostała krawędź, wychodząca z wierzchołka , prowadzi do pewnego wierzchołka odpowiadającego zaprzeczeniu literału wierzchołka , zatem literał wierzchołka ma wartość zero i jest wybrane do pokrycia w trójkącie, w którym występuje. Zatem krawędź też jest pokryta.

W drugą stronę, załóżmy, że dane jest pokrycie. W każdym trójkącie, dla wierzchołka, który nie jest w pokryciu, ustawiamy wartość odpowiedniej zmiennej tak, aby literał w tym wierzchołku był równy 1. Należy zauważyć, że takie wartościowanie jest niesprzeczne. Wynika to stąd, że przeciwne literały zawsze odpowiadają dwóm wierzchołkom z różnych trójkątów połączonych krawędzią. Co najmniej jeden z tych wierzchołków jest w pokryciu, a więc odpowiadający mu literał nie bierze udziału w obliczaniu wartościowania.

Zauważmy, że tak jak i poprzednio, do realizacji redukcji wystarczy pamięć robocza rzędu , co kończy dowód.

End of proof.gif

Klika, zbiór niezależny

Przypomnijmy definicje obu problemów:

Problem [INDEPENDENT SET]

Wejście: Graf nieskierowany , liczba całkowita

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

Wejście: Graf nieskierowany , liczba całkowita

Wyjście: TAK jeśli ma podgraf pełny (klikę) o

wierzchołkach, NIE w przeciwnym przypadku.

Ćwiczenie 3.1

Wykaż, że problem INDEPENDENT SET jest NP-zupełny.
Wskazówka
Rozwiązanie

Ćwiczenie 3.2

Wykaż, że problem INDEPENDENT SET jest NP-zupełny, wykorzystując pokazaną wyżej redukcję z 3SAT do NODE COVER, zmieniając tylko rozumowanie tak, aby odnosiło sie do problemu INDEPENDENT SET.

Ćwiczenie 3.3

Wykaż, że problem CLIQUE jest NP-zupełny.
Wskazówka
Rozwiązanie

Cykl i ścieżka Hamiltona

Problem [HAMILTONIAN CYCLE]

Wejście: Graf nieskierowany

Wyjście: TAK jeśli ma cykl Hamiltona, czyli cykl przchodzący przez każdy wierzchołek dokładnie raz, NIE w przeciwnym przypadku.

Twierdzenie 3.2 [Cykl Hamiltona]

CYKL HAMILTONA jest NP-zupełny.

Gadżet dla HC.
Gadżety i cykl Hamiltona.
Ścieżki gadżetów i cykl Hamiltona.

Dowód

Przynależnośc do klasy NP jest oczywista. Konstruujemy redukcje z problemu NODE COVER. Na wejściu mamy nieskierowany graf oraz liczbę całkowitą . Oznaczmy graf wynikowy jako .

Redukcja przeprowadzona jest techniką gadżetu (w literaturze angielskiej używa sie również terminu widget). Gadżet to fragment struktury wynikowej o określonych własnościach. W naszym przypadku pierwszym krokiem redukcji jest wygenerowanie, dla każdej krawędzi , gadżetu będącego grafem przedstawionym na rysunku Gadżet dla HC.

Jedynie narożne wierzchołki grafu będą połączone z wierzchołkami spoza . Stąd wynika, że jeśli ma cykl Hamiltona, to musi on przechodzić przez tylko na jeden z przedstawionych na rysunku Gadżety i cykl Hamiltona sposobów. Konstrukcja gadżetu uniemożliwia inne usytuowanie cyklu Hamiltona względem (rysunek Gadżety i cykl Hamiltona).

Drugi krok redukcji to wygenerowanie krawędzi w łączących gadżety w tak zwane ścieżki. Dla każdego wierzchołka najpierw porządkujemy dowolnie wszystkie jego sąsiednie wierzchołki, oznaczmy je przez , gdzie jest stopniem wierzchołka . Konstrukcja ścieżki odpowiadającej wierzchołkowi , łączącej wszystkie gadżety odpowiadające krawędziom incydentnym z , dokonuje się przez dołączenie do zbioru krawędzi postaci

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

Kładziemy zatem

W animacji Ścieżki gadżetów i cykl Hamiltona pokazano graf o 4 wierzchołkach i rezultat redukcji. Zacieniowane zostały dwa wierzchołki grafu, które tworzą pokrycie. Pogrubione krawędzie tworzą cykl Hamiltona. Zaczynając od selektora , przechodzimy do początku ścieżki odpowiadającej pierwszemu wierzchołkowi z pokrycia, czyli . Po przejściu gadżetów na tej ścieżce wracamy do , a stąd do początku ścieżki odpowiadającej drugiemu węzłowi z pokrycia, .

Wykażemy, że ma cykl Hamiltona wtedy i tylko wtedy, gdy ma pokrycie o liczności .

Załóżmy, że ma cykl Hamiltona i prześledźmy jego bieg, zaczynając od (w dowolnym kierunku). Następny wierzchołek na cyklu musi być początkiem (lub końcem - załóżmy to pierwsze) ścieżki gadżetów dla pewnego wierzchołka . Dodajemy do generowanego pokrycia. Zgodnie z własnością gadżetu, cykl przebiega całą ścieżkę i na końcu przechodzi do innego selektora, załóżmy, że jest to . Z musi przejść na początek lub koniec innej ścieżki, odpowiadającej wierzchołkowi . Dodajemy do pokrycia i kontynuujemy. Z ostatniej, -tej ścieżki, cykl musi wrócić do . Ponieważ cykl Hamiltona przeszedł przez wszystkie wierzchołki , a więc przez wszystkie gadżety , zatem wybrane w ten sposób wierzchołki stanowią pokrycie.

Teraz załóżmy, że ma pokrycie . Konstruujemy cykl Hamiltona w . Zaczynamy od selektora i przechodzimy na początek ścieżki związanej z , czyli do węzła . Przechodzimy przez kolejne gadżety aż do końca ścieżki. Dla danego gadżetu musimy podjąć decyzję, czy przechodzimy przez wszystkie wierzchołki, czy tylko przez połowę (jedną "ścianę"). Decyzja zależy od tego, czy również należy do pokrycia. Jeśli nie, to przechodzimy cały gadżet; jeśli tak, to drugą "ścianę" pozostawiamy, aby później, gdy trawersowana będzie ścieżka dla również można było przejść przez . Z ostatniego węzła na ścieżce przechodzimy do selektora i powtarzamy konstrukcję. Z ostatniego węzła na -tej ścieżce wracamy do , zamykając w ten sposób cykl Hamiltona.

Ostatnim krokiem dowodu jest stwierdzenie, że konstrukcję grafu można wykonać, posługując się pamięcią roboczą rozmiaru logarytmicznego. Wynika to, jak i w poprzednich dowodach, z tego że maszynie wystarcza pamięć na licznik położenia w wejściowym grafie oraz licznik numeru (nazwy) generowanego wierzchołka i krawędzi grafu .

End of proof.gif

Bardzo podobny w sformułowaniu jest problem ścieżki Hamiltona (HAMILTONIAN PATH). Na weściu jest graf nieskierowany, na wyjściu jest TAK, jeśli w grafie istnieje ścieżka przechodząca przez każdy wierzchołek dokładnie raz. Oczywiste jest, że istnienie cyklu Hamiltona implikuje istnienie ścieżki Hamiltona, jednak są to różne problemy, i NP-zupełność tego drugiego wymaga osobnego dowodu. Tym niemniej, na przykładzie tych problemów można pokazać pewne techniki dowodzenia NP-zupełności w takich przypadkach. Jedną z nich jest modyfikacja znanego już dowodu NP-zupełności problemu podobnego, drugą zaś redukcja z problemu podobnego.

Twierdzenie 3.3 [HAMILTONIAN PATH]

Problem HAMILTONIAN PATH jest NP-zupełny.

Ćwiczenie 3.4

Metoda 1: zmodyfikuj konstrukcję grafu w dowodzie NP-zupełności problemu HAMILTONIAN CYCLE tak, aby stanowił dowód NP-zupełności problemu HAMILTONIAN PATH.

Wskazówka
Rozwiązanie


Ćwiczenie 3.5

Metoda 2: Skonstruuj redukcję z problemu CYKL HAMILTONA.

Wskazówka
Rozwiązanie

Problemy na zbiorach i liczbach

Trójdzielne skojarzenie i pokrycie zbiorami

Uogólnieniem klasycznego problemu skojarzenia w grafie dwudzielnym jest następujący problem:

Problem [TRIPARTITE MATCHING]

Wejście: parami rozłączne równoliczne zbiory o mocy oraz relacja
Wyjście: TAK, jeśli istnieje skojarzenie w , czyli podzbiór taki, że dla dowolnych trójek zachodzi , oraz . NIE w przeciwnym przypadku.

Problem skojarzenia dwudzielnego jest obliczeniowo łatwy. Uogólnienie do trzech wymiarów utrudnia problem radykalnie.

Twierdzenie 4.1 [TRIPARTITE MATCHING]

Problem TRIPARTITE MATCHING jest NP-zupełny.

Gadżet redukcji 3SAT do 3DM.

Dowód

Ponownie mamy do czynienia z dość skomplikowaną konstrukcją posługującą się gadżetami, redukującą problem 3SAT do naszego problemu.

Na wejściu mamy zbiór klauzul nad zmiennymi . Najpierw dla każdej zmiennej konstruujemy gadżet , który będzie odpowiadał za wybór wartościowania tej zmiennej. Składa się on z dwóch zbiorów trójek:




Przykładowy gadżet dla zmiennej w przypadku, gdy liczba klauzul wynosi pokazano na rysunku Gadżet redukcji 3SAT do 3DM. Grubą linią zaznaczono trójki ze zbioru.

Dla każdego gadżetu pierwsze elementy trójek, , występują jeszcze w innych trójkach, które za chwilę zdefiniujemy. Pozostałe elementy występują tylko w danym gadżecie. Zatem, jeśli wybrano skojarzenie, to dla ustalonego gadżetu to skojarzenie zawiera albo cały zbiór i żadnej trójki z , albo na odwrót. W toku dalszego rozumowania, wybór do skojarzenia zbioru będzie oznaczał wartościowanie zmiennej na false i pozostawi niepokryte elementy o indeksach parzystych. Wybór przeciwny ustali wartościowanie na true i pozostawi niepokryte elementy o indeksach nieparzystych. Sytuacja taka została przedstawiona na rysunku Gadżet redukcji 3SAT do 3DM, pogrubioną linią zaznaczono wybór trójek .

Trójki, które zdefiniujemy, teraz mogą być nazwane "składową testowania". Skojarzą one niepokryte elementy z gadżetów z odpowiednimi wystąpieniami literałów w klauzulach. Dla każdej klauzuli składowa testowania zawiera 3 trójki odpowiadajace kolejnym literałom , zdefiniowane następująco: Jeśli to . Jeśli to . Analogicznie dla literałów .

Elementy występują tylko w trzech trójkach zbioru , zatem skojarzenie wybiera dokładnie jedną z tych trójek. Aby móc daną trójkę wybrać, element na pierwszej współrzędnej w tej trójce musi być niepokryty trójkami z odpowiedniego gadżetu. Ale to oznacza, że wartość danego literału jest true, czyli klauzula jest spełniona. Innymi słowy, możliwość pokrycia elementów jest równoważna temu, że istnieje w klauzuli literał o wartości logicznej true.

Skojarzenie wybrane dla gadżetów ma liczność , składowa testowania daje kolejnych trójek w skojarzeniu, zatem ze wszystkich elementów na pierwszej współrzędnej (elementy ) pozostaje nieskojarzonych. Zatem w konstrukcji potrzebna jest jeszcze trzecia "składowa odśmiecania" zdefiniowana nastepująco:



Pozwala ona skojarzyć elementy pozostałe po wyborze wartościowania i testu spełnialności.

Na podstawie opisanej konstrukcji i komentarzy jej towarzyszących możemy już łatwo stwierdzić, że formuła wejściowa posiada wartościowanie spełniające wtedy i tylko wtedy, gdy utworzony w wyniku redukcji zbiór trójek ma skojarzenie.

End of proof.gif

Rozważmy jeszcze trzy podobne problemy na zbiorach. Ich NP-zupełność stanie się oczywista, gdy zauważymy, że stanowią one kolejne uogólnienia problemu trójdzielnego skojarzenia.

Problem [EXACT COVER BY 3-SETS (pokrycie trójelementowymi podzbiorami)]

Wejście: Rodzina trójelementowych podzbiorów zbioru , takiego że dla pewnej calkowitej
Wyjście: TAK, jeśli istnieje podrodzina taka, że każdy element zbioru należy do dokładnie jednego zbioru rodziny , NIE w przeciwnym przypadku.

Ćwiczenie 4.1

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

Rozwiązanie
Problem [SET COVERING (pokrycie zbiorami)]

Wejście: Rodzina podzbiorów zbioru , liczba całkowita
Wyjście: TAK, jeśli istnieje k-elementowa podrodzina rodziny , która pokrywa cały zbiór , w przeciwnym przypadku NIE.

Ćwiczenie 4.2

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

Rozwiązanie

Suma podzbioru i inne problemy liczbowe

Teraz zajmiemy się kilkoma problemami związanymi z liczbami. Najwięcej trudu będzie kosztować udowodnienie NP-zupełności pierwszego z nich - następne pójdą już łatwiej. Ta pierwsza trudność zasadza się na tym, że jak do tej pory dowodziliśmy NP-zupełność tylko dla problemów, w których tak naprawdę nie ma liczb, jako elementów struktury kombinatorycznej. Oczywiście, każde słowo wejściowe może być traktowane jako liczba, kod maszyny Turinga też jest liczbą. Tutaj jednak chodzi o naturalne sformułowanie problemu, w odniesieniu do obiektów abstrakcyjnych takich, jak: liczby, funkcje, relacje, grafy itd. Problematyka trudności obliczeniowej problemów z liczbami jest rozwinięta w następnej lekcji.

Problem [SUBSET SUM (suma podzbioru)]

Wejście: Skończony zbiór elementów, dla każdego elementu waga oraz liczba .
Wyjście: TAK, jeśli istnieje podzbiór taki że , NIE w przeciwnym przypadku.

Twierdzenie 4.2 [SUBSET SUM]

Problem SUBSET SUM jest NP-zupełny.

Dowód

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

Niech . Najpierw ustalamy porządek elementów w zbiorze i zapisujemy każdy zbiór jako wektor -bitowy (czyli jest to struktura danych - wektor bitowy - reprezentująca podzbiór danego zbioru). W każdym wektorze są oczywiście 3 bity równe 1 a pozostałe są zerowe. Następnie przed każdym bitem wstawiamy dodatkowo bitów zerowych i traktujemy ten wektor jako liczbę zapisaną binarnie. Powstaje w ten sposób liczb -bitowych - są to wagi elementów zbioru Y. Liczba jest również takiej długości, powstaje przez wypisanie jedynek, a następnie wstawienie przed każdą jedynką zer.

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

Bloki zer dodane przed każdym bitem reprezentacji wektorowej podzbioru gwarantują, że sumując dowolny podzbiór wygenerowanych liczb, nie napotkamy na przeniesienie poza taki blok zer. A zatem, jeśli istnieje podzbiór liczb dający w sumie , to wszystkie te liczby w swoich rozwinięciach binarnych zawierają w sumie tyle jedynek, ile jest ich w , na różnych pozycjach. A więc odpowiadajace tym liczbom podzbiory pokrywają cały zbiór .

Zatem opisane przekształcenie jest redukcją. Jak w poprzednich dowodach, potrzebna jest pamięć robocza jedynie na stałą liczbę liczników. A więc jest to redukcja logarytmiczna.

End of proof.gif

W tej części lekcji wykażemy NP-zupełność dwóch podobnych problemów liczbowych.

Problem [PARTITION (podział)]

Wejście: Skończony zbiór elementów oraz dodatnia całkowita waga każdego elementu.
Wyjście: TAK, jeśli istnieje podzbiór , taki że , NIE w przeciwnym przypadku.

Ćwiczenie 4.3

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

Wskazówka
Rozwiązanie
Problem [KNAPSACK (plecak)]

Wejście: Skończony zbiór elementów, rozmiar i wartość dla każdego elementu, ograniczenie pojemności oraz żądana wartość .
Wyjście: TAK, jeśli istnieje podzbiór , taki że oraz , NIE w przeciwnym przypadku.

Ćwiczenie 4.4

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

Wskazówka
Rozwiązanie

Podsumowanie technik dowodów NP-zupełności

Najprostsze redukcje otrzymujemy metodą zacieśnienia. Przez narzucenie dodatkowych zależności w instancjach problemu, o którym dowodzimy NP-zupełności, otrzymujemy instancje znanego problemu NP-zupełnego. W ten sposób wykazujemy, że nasz problem jest uogólnieniem problemu znanego, a więc nie jest od niego łatwiejszy. Przykłady takich redukcji zastosowaliśmy do problemów: EXACT COVER BY 3SETS, SET COVERING, KNAPSACK.

Pozostałe dowody można by zaliczyć do metody gadżetów. Fragmenty instancji problemu wejściowego przekształca się we fragmenty instancji probelmu wynikowego (gadżety) i wiąże się zależnościami (innymi gadżetami), których zachodzenie w problemie wynikowym ma mieć ścisłe odzwierciedlenie w spełnieniu wymagań problemu źródłowego. Czasem gadżet jest trywialny (np. w redukcji SUBSET SUM do PARTITION jest to ta sama waga elementu), kiedy indziej dość naturalny i nietrudny (SAT DO 3SAT), czasem bardzo pomysłowy (VERTEX COVER do HAMILTONIAN CYCLE, 3SAT do TRIPARTITE MATCHING, 3SAT do MAX2SAT).

Ćwiczenia końcowe

Ćwiczenie 6.1

Wykaż, że następujący problem izomorfizmu podgrafu jest NP-zupełny:

Problem [SUBGRAPH ISOMORPHISM]

Wejście: , - grafy nieskierowane.
Wyjście: TAK, jeśli ma podgraf izomorficzny z , NIE w przeciwnym przypadku.

Wskazówka
Rozwiązanie

Ćwiczenie 6.2

W tym ćwiczeniu pytamy o trudność obliczeniową problemu pochodzącego z teorii szergowania. Wykaż, że NP-zupełny jest następujący problem:

Problem [SEQUENCING WITHIN INTERVALS]

Wejście: Zbiór zadań , dla każdego zadania trzy liczby całkowite: długość zadania , moment pojawienia się ,oraz ograniczenie czasowe
Wyjście: TAK, jeśli wszystkie zadania można wykonać na jednym procesorze, bez przerywania, spełniając ograniczenia czasowe, NIE w przeciwnym przypadku. Formalnie, pytamy o funkcję alokacji przydzielająca każdemu zadaniu czas rozpoczęcia wykonywania taki, że oraz , dla każdego zadania .

Wskazówka
Rozwiązanie

Ćwiczenie 6.3

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

Problem [FEEDBACK VERTEX SET]

Wejście: Graf skierowany , liczba całkowita .
Wyjście: TAK, jeśli istnieje w podzbiór -wierzchołkowy, taki że graf pozostały po usunięciu tego podzbioru jest acykliczny.
Udowodnij, że FEEDBACK VERTEX SET jest NP-zupełny.

Wskazówka
Rozwiązanie

Ćwiczenie 6.4

Kolorowanie (wierzchołkowe) grafu jest klasycznym problemem optymalizacyjnym w teorii grafów. Przypomnijmy, że chodzi o przypisanie wierzchołkom grafu nieskierowanego kolorów tak, aby końce każdej krawędzi miały różne kolory, a liczba kolorów była możliwie najmniejsza.

Okazuje sie że nawet jeśli ustalimy żądaną liczbe kolorów na 3, to problem jest NP-zupełny. Dowód tego faktu nie jest natychmiastowy.

Problem [3COLORING]

Wejście: Graf nieskierowany .
Wyjście: TAK, jeśli istnieje funkcja taka, że dla każdej krawędzi , .
Za pomocą redukcji z problemu 3SAT udowodnij, że problem trójkolorowania jest NP-zupełny.

Wskazówka
Rozwiązanie

Testy końcowe