Theory of NP-Completeness - a rough guide

by gibffe ( have fun =] )

Poniżej, zebrane są wiadomości ze skryptu pana M.Kubale, które wydały mi się szczególnie interesujące, ewentualnie całkiem zabawne. Cała ta teoria jest dość zabawna a kolokwium będzie, że tak się wyrażę, komiczne =]. Jeśli ktoś poczuje, że to co tu napisałem pomogło w z zaliczeniu 2 kolokwium, czekam na dary. [e-mail] over&out

++ algorytmy decyzyjne ++

Algorytmy decyzyjne to takie algorytmy, które na wyjściu zwracają jedną z dwóch wartości - `true' albo `false'. Ich odpowiedz jest zatem binarna. Okazuje się, że wiele problemów optymalizacyjnych można łatwo sprowadzić do problemów decyzyjnych - i jeżeli dany problem decyzyjny da się rozwiązać w czasie wielomianowym, to odpowiadający mu problem optymalizacyjny również posiada wielomianową złożoność. W przeciwnym razie, o problemie optymalizacyjnym możemy śmiało powiedzieć, że ma złożoność gorszą od wielomianowej. Bardzo często problemy decyzyjne formułuje się jako pytania „czy istnieje”. Ex: „czy istnieje pokolorowanie grafu korzystające z ę kolorów”, „czy w grafie G istnieje zbiór niezależny składający się z ź wierzchołków” i tym podobne.

Okazuje się, że dla wielu `trudnych' problemów łatwiej jest sprawdzić czy zaproponowane rozwiązanie jest poprawne niż znaleźć takie rozwiązanie od zera. Dla problemu decyzyjnego P rozwiązanie `r' będziemy rozumieć jako obiekt pewnego typu. Obiekt ten może lub nie spełniać określone przez problem kryterium. Zaproponowane rozwiązanie `r' możemy rozumieć jako skończony ciąg symboli pewnego, skończonego alfabetu. Sprawdzenie, czy `r' spełnia problem P będzie się sprowadzało do sprawdzenia, czy ciąg symboli jest `sensowny' i spełnia pewne warunki.

Niech x - `yes instance' problemu P. O co chodzi? Ex: nie P brzmi następująco: [ mamy na wejściu graf G, czy ten graf jest grafem hamiltonowskim ?], wtedy `yes instance' x będzie po prostu hamiltonowskim grafem. `no instance' x będzie grafem G który nie jest hamiltonowski.

def: Mając problem decyzyjny P, `układem dowodowym' dla P nazwiemy zbiór S par (`x' , `r') takich, że dla każdej `yes instance' x dla P znajdzie się przynajmniej jedno rozwiązanie(dowód) `r' takie, że (`x', `r') ∈ S

Ex: nasze `yes instance' x będzie grafem Hamiltonowskim, problemem P będzie problem podany wcześniej „czy G jest hamiltonowski”, a dowodem `r' będzie cykl hamiltona.

Układ dowodowy będzie układem wielomianowym, jeżeli istnieje wielomianowy algorytm A sprawdzający czy (`x', `r') ∈ S. Innymi słowy, A ma sprawdzić czy zaproponowany dowód `r' jest prawdziwy.

Dla podanego przykładu, jasne jest, że potrafimy w czasie wielomianowym sprawdzić czy zaproponowany cykl `r' jest cyklem hamiltona i tym samym stwierdzić czy G jest hamiltonowski, czy też nie.

++ algorytmy niedeterministyczne - szkic =] ++

Do tej pory używaliśmy algorytmów, dla których wartość zwracaną można było przewidzieć ze 100 % pewnością. Innymi słowy dla określonych danych wejściowych `d' obiekt wyjściowy `o' był taki sam, niezależnie od liczby uruchomień algorytmu A.

Wyjście algorytmu niedeterministycznego jest nieprzewidywalne. Oczywiście jest ono zawsze w pewnych granicach, np. jest to zawsze pewien obiekt ze skończonego zbioru, ale nigdy nie wiemy, który obiekt pojawi się na wyjściu.

Algorytmy niedeterministyczne używają trzech `nowych' poleceń:

Choice(S) - wybierz jeden z elementów zbioru S

Failure - sygnalizuje niepowodzenie

Success - sygnalizuje sukces

Przypisanie x = Choice(&x, n) oznacza wybór jednego z n elementów począwszy od adresu &x do &x+n-1. Sygnały Failure i Success działają jak exit(-1) oraz exit(1) . Złożoności czasowe operacji Choice(S), Failure oraz Success są O(1).

Ex: problem szukania elementu `x' w liście elementów L:

(…)

obiekt j;

obiekt *L = (objekt *) malloc(N*sizeof(objekt));

wpisz_obiekty(L,N);

j = Choice(L, N);

if ( L[j] == x )

{

printf(“success\n”);

Success;

}

else Failure;

Jak nietrudno zauważyć niedeterministyczne algorytmy sux =]

def. Algorytm niedeterministyczny ma złożoność obliczeniową O( f(n) ) jeżeli dla każdego wejścia rozmiaru n > n₀ dla którego algorytm generuje sygnał `success', czas potrzebny na wygenerowanie tego sygnału jest maxymalnie cf(n) dla pewnych stałych c oraz n_0.

Każdy algorytm niedeterministyczny składa się z dwóch faz:

1. Faza niedeterministyczna.

Tutaj dokonany jest pewien ciąg instrukcji `choice' czego wynikiem jest skończony ciąg `s' symboli skończonego alfabetu, zapisany gdzieś w pamięci.

2. Faza deterministyczna.

Algorytm deterministyczny, sprawdza czy `s' jest `ok.' tzn. czy spełnia jakieś tam warunki i kończy działanie sygnałem Failure lub Success.

++ klasy P oraz NP ++

def. P jest klasą problemów decyzyjnych, które są `ograniczone wielomianowo'. Innymi słowy dla każdego problemu z klasy P istnieje algorytm go rozwiązujący który działa w czasie wielomianowym.

Pomimo że P ogranicza się tylko do problemów decyzyjnych, łatwo jest odnieść się do problemów optymalizacyjnych. Ex: dla problemu sortowania, jego wersja decyzyjna będzie „mamy dwie sekwencje liczb int, czy druga sekwencja jest posortowaną wersją pierwszej” itp.

Dla każdego realistycznego systemu liczącego (czytaj komputera) można stwierdzić, że jeżeli problem `p' nie należy do klasy problemów P, to jest problemem trudnym.

def. NP jest klasą problemów decyzyjnych, które `przyjmują' wielomianowy układ dowodowy. Prawdopodobnie chodzi o to, że są tu (w NP) problemy, dla których trudno jest znaleźć rozwiązanie w wielomianowym czasie, ale w takim czasie można sprawdzić każde jedno zaproponowane. Sux, ogólnie to nie wiem czy to jest prawda czy nie.

++ problemy NP-zupełne [shit happens] ++

Nieformalnie: mówi się, że problemy np-zupełne są to najtrudniejsze problemy w klasie NP. Jeżeli znajdzie się algorytm działający w czasie wielomianowym dla któregokolwiek problemu np-zupełnego, wtedy każdy problem w klasie np da się rozwiązać algorytmem wielomianowym.

+| Redukcje |+

Chcemy rozwiązać problem P1, oraz mamy algorytm rozwiązujący problem P2. Mamy również funkcję T, która pobiera dane wejściowe x dla problemu P1, dokonuje na nich pewnych operacji T(x) po czym przesyła dane T(x) do problemu P2. Dane T(x) mają taką własność, że P1(x) zwraca `true' wtedy i tylko wtedy gdy P2( T(x) ) zwraca `true'. Łatwo teraz zauważyć, że przy pomocy T(x) oraz P2 można rozwiązać P1.

[redukcja] Ex: niech P1: „mamy dwie liczby całkowite (j , k), 1 < j < k , czy j jest dzielnikiem k ?”, niech P2: „mamy sekwencję n liczb, n ≥ 2. czy ta sekwencja jest uporządkowana rosnąco ?”

Postać T(x):

T( l1 , l2) = (0 , 1) gdy j | k

T( l1 , l2) = (2 , 1) gdy j nie jest dzielnikiem k

/* zakładam tutaj, że sekwencja 0, 1 jest sekwencją uporządkowaną rosnąco */

Niech j = 3, k = 12. T(3 , 12) = (0 , 1) , P2(0 , 1) -> true

Niech j = 5, k = 12 T(5 , 12) = (2 , 1), P2(2 , 1) -> false

Widać, że P2 połączony z T rozwiązuje P1. Przykład totalnie z dupy, wzięty żywce ze skryptu. Bo skoro T dysponuje operacją | to niby czemu sam P1 nią nie dysponuje ?! sux…

def. niech T będzie funkcją pobierającą dane wejściowe x problemu P1, dokonującą transformacji T(x) której wynik będzie podany na wejście problemu P2. T nazwiemy redukcją wielomianową z P1 na P2, gdy:

1. operacje wykonywane przez T da się wykonać w czasie wielomianowym

2. T `nie zmienia' problemu. Dla każdego x zachodzi P1(x) = P2( T(x) )

Problem P1 jest wielomianowo redukowalny do P2, gdy istnieje wielomianowa transformacja z P1 do P2. Taką redukcję oznaczamy P1 α P2.

+| jeżeli P1 α P2 oraz P2 ∈ P wtedy P1 też jest w P |+

def. problem Z nazwiemy NP-zupełnym, jeżeli jest w klasie problemów NP, oraz każdy inny problem Z^'' z NP jest wielomianowo redukowalny do Z -> zachodzi Z^'' α Z

+| CNF |+

CNF, inaczej Conjuctive normal form to wyrażenie logiczne postaci:

/* nawiasów może być oczywiście więcej, ale w każdym nawiasie są 3 elementy ze skończonego zbioru X zmiennych bool */

xi mogą przyjmować wartości 1 lub 0.

def. problem spełnialności (SATISFIABILITY) formułuje się następująco: „czy istnieje taki sposób nadania zmiennym xi wartości `true' lub `false' by wyrażenie logiczne jako całość miało wartość true ?” Problem decyzyjny zwany cnf-spełnialnością to problem spełnialności w którym wyrażenie logiczne jest wyrażeniem typu CNF [ patrz wyżej ].

W roku 1971 niejaki pan Cook znalazł pierwszy problem np-zupełny. Stwierdził on, że problem cnf-spełnialności jest takim właśnie problemem. Można pokazać, że problem cnf-spełnialności jest w klasie NP. Dowód, że cnf-s jest w klasie npc (np-complete) został w skrypcie pominięty, a jakże… sux

procedure cnf-s

begin

for i = 1 to n do

xi = choice(true, false)

if CNF is true the Success

else Failure

end.

No czy to nie piękne ? Jak na moje, to każdy algorytm, w którym użyję random(x) będzie w klasie np. Ale zapewne się mylę. Nagle, w roku 71 jakiś problem (dla ustalenia uwagi cnf-spełnialność) staje się problemem npc i .. i ogólnie sux…

++ dowodzenie np-zupełności ++

Aby pokazać, że problem Z jest npc, należy:

1. wybrać problem K o którym wiadomo, że jest npc

2. dokonać redukcji K α Z

3. `wykumać' że skoro dokonaliśmy redukcji z pkt.2 to każdy problem z NP można

zredukować do Z

4. pokazać, że Z jest w klasie NP - algorytm niedeterministyczny albo `wielomianowy układ

dowodowy' lub pokazać redukcję Z α K

=] r0x.

++[Przegląd problemów NPC]++

Liczba chromatyczna: dany jest graf G oraz pewna liczba naturalna k. „czy graf G jest

k- kolorowalny ?” Problem pozostaje w klasie npc nawet dla k = 2, oraz gdy G jest grafem planarnym.

Indeks chromatyczny: dany jest graf G oraz liczba naturalna k. „czy graf G jest krawędziowo

k-kolorowalny ?” Jest to problem podobny do poprzedniego, z tą różnicą, że kolorujemy krawędzie a nie wierzchołki. Ten problem jest w klasie npc nawet dla grafów planarnych.

Liczba klikowa: dany jest graf G oraz liczba naturalna k. „czy dany graf zwiera k-

elementową klikę ?”. Klika wielkości k jest to k wierzchołkowy podgraf pełny G' grafu G. A graf pełny to taki graf w którym każdy wierzchołek jest połączony z każdym innym. Generalnie jest to problem npc, choć dla wielu grafów, np. grafów planarnych jest problemem wielomianowym.

Zbiór niezależny: dany jest graf G oraz liczba naturalna k. „czy graf G zawiera k-elementowy zbiór niezależny ?„ Jeżeli zbiór B ⊆ V wierzchołków grafu G jest niezależny, to żaden wierzchołek należący do B nie jest połączony z żadnym innym z B. Ten problem jest npc, nawet gdy założymy, że G jest kubiczny grafem planarnym.

Pokr. wierzchołkowe: dany jest graf G oraz liczba naturalna k. „czy graf G posiada

co najwyżej k-elementowe pokrycie wierzchołkowe?” Pokryciem wierzchołkowym w grafie G nazwiemy zbiór B ⊆ V taki, że każda krawędź grafu G jest incydentna z co najmniej jednym

wierzchołkiem z B . V jest zbiorem wszystkim wierzchołków. Dla Δ(G) <= 2 jest to problem P. dla Δ(G) >= 3 jest to problem npc. Według pana R.J dla grafów planarnych jest to problem npc nawet gdy Δ(G) <= 4.

Dwudzielny podgraf: dany jest graf G oraz liczba naturalna k. „czy graf G zawiera podgraf dwudzielny o co najmniej k krawędziach ?” Grafem dwudzielnym nazwiemy taki graf G, w którym istnieją takie rozłączne zbiory niezależne V1 oraz V1 ⊆ V, że V1 ∪ V1 = V.

Mowa tu o zbiorach wierzchołków. Inna def. dwudzielności jest taka: graf G jest dwudzielny, wtedy i tylko wtedy, gdy każdy cykl w nim zawarty jest cyklem parzystym.

Ten problem jest npc, nawet gdy założymy, że G jest grafem podkubicznym. Jest on wielomianowy, gdy k >= m(G). gdzie m(G) to liczba krawędzi grafu. Graf podkubiczny, to taki graf, którego stopień Δ(G) = 0 v 1 v 2 v 3. Warto wspomnieć, że graf kubiczny to graf 3-regularny, czyli deg(v) = 3 dla każdego wierzchołka v.

Planarny podgraf: ponownie, dany jest graf G oraz liczba naturalna k. „czy graf G zawiera podgraf planarny o co najmniej k krawędziach ?” Jest to problem npc, choć podobno staje się wielomianowy, gdy k >= m(G). m(G) to prawdopodobnie liczba krawędzi, ale mogę się mylić.

Graf hamiltonowski: dany jest graf G. „czy ten graf jest grafem Hamiltonowskim ?”. Graf Hamiltonowski, to taki graf w którym pewna droga zamknięta zwiera wszystkie jego wierzchołki. Droga zamknięta to taki łańcuch w którym wszystkie wierzchołki są różne (poza co najwyżej początkowym i końcowym).

Ten problem jest npc, nawet gdy założymy, że G jest grafem dwudzielnym.

Graf półhamiltonowski: dany jest graf G. „czy ten graf jest półhamiltonowski ?”. Grafem półhamiltonowskim nazwiemy taki graf, który zawiera ścieżkę(drogę) zawierającą wszystkie jego wierzchołki. W grafie hamiltonowskim ta droga jest zamknięta, w półhamiltonowskim nie. Jest to problem npc, nawet gdy G będzie grafem dwudzielnym.

Wspólny podgraf: dane są grafy G i H, oraz liczba naturalna k. „czy grafy G i H posiadają izomorficzne podgrafy o co najmniej k krawędziach?” Ten problem jest npc, nawet dla grafów pełnych.

Drzewo spinające: dany jest graf G oraz liczba naturalna k. „czy graf G posiada drzewo spinające posiadające co najmniej k liści?” Drzewo spinające to taki podgraf grafu G, który zawiera wszystkie jego wierzchołki i jest drzewem, czyli grafem acyklicznym. Ten problem jest npc nawet dla grafów planarnych.

Problem komiwojażera: dany jest graf obciążony (G,ω) oraz liczba naturalna d. „czy istnieje ścieżka przechodząca przez wszystkie wierzchołki grafu G której długość <= d ?” Jest to problem npc, nawet gdy założymy, że wagi wszystkich krawędzi <= 2.

Podział zbioru: dany jest skończony zbiór A oraz funkcja s:A→N. „czy istnieje taki zbiór B⊆A, że zachodzi:

Jest to problem npc, choć można go rozwiązać algorytmem pseudowielomianowym.

suma podzbioru: dany jest zbiór skończony A, funkcja s:A→N i liczba naturalna k. „czy istnieje taki zbiór B ⊆ A, że

?”. Ten problem jest npc, ale można go rozwiązać algorytmem pseudowielomianowym.

problem plecakowy: dany jest skończony zbiór obiektów A, funkcje s,v:A→N, oraz liczby naturalne k i l. „czy istnieje taki zbiór obiektów B ⊆ A że zachodzi:

?”. Ten problem jest npc, ale można go rozwiązać algorytmem pseudowielomianowym.

-smack my bitch up!-

warcaby: dana jest liczba naturalna n i zgodne z regułami rozstawienie figur na planszy do gry w warcaby o wymiarach nxn. Jest również dana informacja o tym kto wykonuje następny ruch. „czy dana sytuacja jest wygrana dla białych ?”. Jest to problem npc.

3-SAT: mamy zbiór C1, …, Cm zdań logicznych zbudowanych z x1….xn zmiennych logicznych przy pomocy operatorów sumy logiczne oraz negacji.

ex:
itd. Warunkiem jest, by w każdym zdaniu Ci znalazły się dokładnie 3 zmienne logiczne. „czy można tak dobrać wartości tych zmiennych, by wszystkie zdania C1,…,Cm miały wartość `true' ?”

Zgodnie z wykładem R.Janczewskiego, można przedstawić `prosty' przepis na dowodzenie, że dany problem jest npc. Skrypt pana M.Kubale traktuje to zagadnienie dość zawile i mało przejrzyście(patrz wyżej+skrypt).

przepis: jeżeli problem P1 ⊆ NP oraz problem P2 ⊆ NPC to P1 jest również NPC gdy można pokazać redukcję P2 α P1 czyli możemy pokazać że problem o którym wiemy, że jest npc można rozwiązać za pomocą problemu, o którym wiemy na pewno, że jest np.

Aby pokazać, że P1 jest w NP należy skonstruować algorytm niedeterministyczny który rozwiązuje zagadnienie P1 w czasie wielomianowym[ten krok się w zasadzie pomija].

Aby pokazać redukcję P2 α P1 trzeba się trochę orientować które problemy należą do npc oraz zgłębić tajną sztukę przeprowadzania redukcji wielomianowych w rozsądnym czasie =]

Istnieją generalnie trzy techniki dowodzenia np-zupełności: `ograniczanie' , `lokalna zamiana' oraz `projektowanie części składowych'.

++ograniczanie++

(cyt.) Technika zwana ograniczaniem jest najprostszą i co więcej, bodajże najczęściej stosowaną metodą dowodzenia NP-zupełności. Ogólnie mówiąc, metoda ta polega na wykazaniu, że badany problem P1 zawiera znany problem NP-zupełny P2 jako przypadek szczególny. Nazwa tej wzięła się z tego, że zasadniczym elementem przeprowadzanego dowodu jest zazwyczaj takie ograniczenie zbioru danych wejściowych dla problemu P, aby stał się on identyczny z problemem P2

Generalnie trzeba chyba przerobić trochę przykładów by się w tym wyćwiczyć bo trudne to w

zasadzie nie jest.

++lokalna zamiana++

(cyt.) Stosując tę technikę dowodzenia NP-zupełności, dzieli się dane wejściowe dla znanego

problemu NP-zupełnego na jednostki podstawowe; następnie korzystając z tych samych reguł zamienia się każdą z nich na jakiś fragment danych wejściowych dla problemu, którego NP-zupełność dowodzimy. Nazwa tej metody wzięła się z tego, że zamiana jednostek podstawowych następuje lokalnie - żadna z zamian nie wpływa na inne zamiany.

Zagadnienia problemów np-trudnych w tym wydaniu sobie podarujemy. Jeżeli zdarzy się tak, że trzeba będzie wznowić ten `guide' ( =[ ) wtedy na pewno coś nowego się tu znajdzie.

Polecam rozwiązanie(o ile to możliwe) zadań z rozdziałów 8 i 9 wykładu R.J.

powodzenia !

|[0][0][1][1][0][0][1][1][0]|
|[1][1][0][0][1][1][0][0][1]|
|[0][0][1][1][0][0][1][1][0]|
   ::   [e-mail]    ::
   ::   gg#5920291    ::

---