Problemy obliczeniowo trudne, teoria NP-zupełności

Problem obliczeniowo łatwy:

posiada algorytm o wielomianowej złożoności czasowej

Przykłady:

- sortowanie listy

- wyszukiwanie elementu w zbiorze

- znajdowanie najkrótszych ścieżek w grafie

- rozwiązywanie układu równań liniowych

Problem obliczeniowo trudny:

nie posiada algorytmu o wielomianowej złożoności.

Znaczenie zagadnienia:

Problemu trudnego obliczeniowo nie da się rozwiązać, nawet na najszybszych komputerach, nawet dla danych umiarkowanego rozmiaru, i najprawdopodobniej nigdy nie będzie się dało.

Teoria złożoności obliczeniowej posługuje się formalnym modelem obliczeń (najczęściej: maszyną Turinga), i dotyczy rozpoznawania języków formalnych. W praktyce wygodniej posłużyć się pojęciem:

Problem decyzyjny Q:

Określony jest przez: opis instancji (czyli danych wejściowych) w terminach zbiorów, relacji, liczb itp. oraz pytanie typu „tak-nie”.

Formalnie:

Zbiór instancji D(Q) - dziedzina problemu.

Podzbiór Y(Q) ⊆ D(Q instancji, na które odpowiedź brzmi "tak".

Rozwiązanie problemu decyzyjnego: algorytm, który dla każdej instancji kończy obliczenie z prawidłową odpowiedzią "tak-nie".

Formalnie: algorytm odpowiada maszynie Turinga, rozpoznającej język słów, które są opisami instancji z podzbioru Y(Q)

Przykład: problem komiwojażera (TSP):

I: n - liczba miast, d(i,j) ∈N - odległość, dla każdej pary miast (i,j), oraz ograniczenie B ∈N.

?: istnieje droga komiwojażera o długości nie większej niż B, przechodząca przez każde miasto dokładnie raz i wracająca do miejsca startowego.

Przykładowe rozwiązanie problemu komiwojażera :

Rozważyć każdą permutację zbioru miast i sprawdzić, czy któraś z nich definiuje wymaganą ścieżkę; jeśli znajdzie się taka to odpowiedz “tak”, w przeciwnym przypadku “nie”.

Złożoność: rzędu co najmniej n! , dyskwalifikująca rozwiązanie dla celów praktycznych

Wersje decyzyjne problemów vs. wersje optymalizacyjne:

OPT-TSP:

dla podanych odległości d(i,j) znajdź najkrótszą drogę komiwojażera.

Wersje optymalizacyjne na ogół bardziej praktyczne, nie są łatwiejsze obliczeniowo (trudniej jest policzyć globalne optimum).

Zatem wykazanie, że dany problem decyzyjny jest trudny implikuje, że skojarzony z nim problem optymalizacyjny też jest trudny.

Metoda ogólna dowodzenia trudności obliczeniowej problemu decyzyjnego Q:

udowodnić, że Q jest nie łatwiejszy obliczeniowo niż inny problem R, który wcześniej ktoś udowodnił. że jest trudny.

Narzędzie do takiego dowodu: transformacja wielomianowa.

Transformacja wielomianowa

przekształcenie danych, (czyli instancji) problemu R w dane dla problemu Q tak, by pokazać, że Q jest nie łatwiejszy niż R.

Formalnie oznaczamy: R ∝ Q

Problem decyzyjny R jest wielomianowo transformowalny do problemu Q, jeśli istnieje funkcja F : D(R) D(Q), realizowalna algorytmem o złożoności wielomianowej, taka, że

∀I∈D(R): I∈Y(R) ⇔ f(I)∈Y(Q)

Problem cyklu Hamiltona (HC):

I: Graf niezorientowany G

?: G ma cykl Hamiltona (cykl przechodzący przez każdy wierzchołek dokładnie raz)

Fakt: HC ∝ TSP

Dowód: konstruujemy funkcję F

argument funkcji F: instancja HC, czyli graf G=(V,E)

wartość funkcji F: instancja TSP, czyli n, d(i,j), B

n = V 

d(i,j) = 1, jeśli (i,j) jest krawędzią w grafie

2, w przeciwnym przypadku

B = n (koniec definicji funkcji F)

• Funkcję F łatwo zrealizować algorytmem wielomianowym.

• G ma cykl Hamiltona ⇔ Komiwojażer ma ścieżkę o długości B.

Koniec dowodu.

Wniosek: jeśli miałabym algorytm A wielomianowy dla TSP, to składając F z A dostałbym również algorytm wielomianowy dla HC (czyli TSP jest trudniejszy niż HC).

Własność transformacji wielomianowej:

Jeśli R ∝ Q to: 1. Q łatwy R łatwy

2. R trudny Q trudny

Klasy problemów P i NP

Klasa P: (polynomial)

Ogół problemów decyzyjnych rozwiązywalnych w czasie wielomianowym (problemy obliczeniowo łatwe)

Klasa NP: (nondeterministic polynomial)

Ogół problemów decyzyjnych rozwiązywalnych w czasie wielomianowym algorytmem niedeterministycznym.

Algorytm (komputer) niedeterministyczny:

Model czysto abstrakcyjny. Posiada dwie fazy obliczeń:

1. zgaduje dowolny obiekt (fizycznie: ciąg znaków, np. bitów), zapisuje go w pamięci roboczej

2. wykonuje obliczenia traktując, jako dane wejściowe oryginalną instancję oraz zapisany obiekt.

Definicja : algorytm niedeterministyczny K rozwiązuje problem decyzyjny Q jeśli dla każdej instancji I zachodzi:

• I∈Y(Q) istnieje taki obiekt, że jeśli zostanie odgadnięty, to algorytm zakończy się akceptacją

• I ∉ Y(Q) dla dowolnego odgadniętego obiektu algorytm odpowie “nie”

Algorytm niedeterministyczny inaczej:

sprawdzenie, czy dany obiekt jest “świadkiem” faktu, że I∈Y(Q).

Komiwojażer - alg. niedeterministyczny:

1. Zgadnij ciąg wierzchołków

2. Sprawdź, czy ciąg ten jest poprawną drogą komiwojażera o odpowiedniej długości, i jeśli tak - odpowiedz “tak', wpp. “nie”.

Złożoność: O(n) - wielomianowa, TSP ∈ NP.

Równoważna definicja klasy NP:

NP to ogół problemów decyzyjnych, których rozwiązania są weryfikowalne w czasie wielomianowym

(to ile trwa znajdowanie tych rozwiązań jest tutaj nieistotne).

Fakt: P ⊆ NP

(bo każdy zwykły algorytm deterministyczny, może być traktowany jakoniedeterministyczny, który pomija odgadnięty obiekt)

Fakt (z życia):

Dla wielu problemów z klasy NP (w tym: TSP), mimo usilnych starań, nie znaleziono algorytmu wielomianowego, stąd hipoteza:

Hipoteza: NP - P ≠ ∅

czyli: w klasie NP są problemy obliczeniowo trudne. Próbą ich charakteryzacji jest definicja klasy NPC.

Klasa NPC (inaczej: NP - zupełne)

Problem Q jest NP-zupełny, jeśli:

1. Q ∈ NP, oraz

2. ∀ R∈NP : R ∝ Q

Problem NP-zupełny jest najtrudniejszy w NP, tzn. jeśliby posiadał algorytm wielomianowy, to wszystkie problemy w NP byłyby łatwe.

Jeśli hipoteza jest prawdziwa, to problemy NP-zupełne są trudne obliczeniowo.

Przy aktualnym stanie wiedzy:

problem NP-zupełny traktowany jest jako trudny obliczeniowo.

Największy nierozstrzygnięty problem informatyki teoretycznej:

P ≠ NP ???

Jak stwierdzić, że dany problem Q jest NP-zupełny ?

1. Znaleźć go na liście w podręczniku do algorytmiki, albo

2. Wykazać samemu

metoda: dobrać R ∈ NPC i skonstruować transformację R ∝ Q,

Np. Wykazano, że HC jest NP-zupełny. Pokazaliśmy, że:

1. TSP ∈ NP.

2. HC ∝ TSP

TSP jest NP-zupełny

Skąd wziął się pierwszy problem NP-zupełny ?

Problem spełnialności formuł logicznych (SAT):

I: formuła zdaniowa nad pewnymi zmiennymi logicznymi, w koniunkcyjnej postaci normalnej, np. ( x oznacza "nie x")

(x₁∨x₂∨x₄) ∧ (x₂∨x₃) ∧ (x₁∨x₂∨x₃∨x₄) ∧ (x₂∨x₄)

?: czy istnieje przypisanie zmiennym wartości 0, 1 tak, by formuła była spełniona

Twierdzenie (Cook, 1971):

SAT jest NP-zupełny

Dowód: zapis za pomocą formuły logicznej faktu, że dana niedeterministyczna maszyna Turinga akceptuje słowo wejściowe x.

Niestety, najprawdopodobniej w NP są jeszcze problemy pośrednie: ani łatwe, ani NP-zupełne.

Twierdzenie (Ladner 1976)

Jeśli P ≠ NP to NP - (P ∪ NPC) ≠ ∅

Jeśli trafimy na taki problem, nic o nim nie potrafimy powiedzieć (chyba że przy okazji rozwiążemy problem czy P ≠ NP).

Przykłady problemów NPC:

• Cykl Hamiltona (ale cykl Eulera jest łatwy)

• Komiwojażer

(ale najkrótsze ścieżki oraz min. drzewo rozpinające są łatwe)

• Pokrycie wierzchołkowe

dla danego grafu i liczby K, czy istnieje podzbiór K wierzchołków taki, że każda krawędź ma przynajmniej jeden koniec w tym zbiorze

• Kolorowanie grafu

I: G = (V,E) graf niezorientowany, K - liczba naturalna

?: G jest K-kolorowalny, tzn. każdemu wierzchołkowi można przypisać kolor tak, aby końce każdej krawędzi miały różne kolory, używając nie więcej niż K kolorów.

Szczególny przypadek: kolorowanie mapy. Każda mapa jest 4-kolorowalna, ale problem, czy jest 3-kolorowalna jest NPC.

Układanie harmonogramu zajęć może być sprowadzone do kolorowania.

• Pokrycie zbiorami

znaleźć możliwie najmniejszą podrodzinę rodziny podzbiorów, aby pokryty został każdy element zbioru (crew scheduling !)

• Izomorfizm podgrafu

dane grafy G, H, pytanie czy G ma podgraf identyczny z H

(częste zastosowanie: sztuczna inteligencja, rozpoznawanie obrazów)

• Klika (szczególny, nadal trudny przypadek poprzedniego):

znaleźć największy podgraf, w którym każdy z każdym jest połączony krawędzią

• Podział

Dany zbiór elementów o podanych wagach. Czy da się podzielić je na dwa rozłączne podzbiory, których suma wag jest taka sama?

• Plecak

Zbiór elementów o podanych wagach i wartościach, żądana wartość V i pojemność plecaka B. Czy istnieje podzbiór elementów, których suma wag nie przekracza B, a suma wartości wynosi, co najmniej V?

• Szeregowanie czynności - wiele wersji, np.:

I: n zadań, m stanowisk, każde zadanie musi przejść przez stanowiska 1,....,m , w tej kolejności, zadanie i-te zajmuje na stanowisku j-tym t(i,j) czasu,

oraz dane jest ograniczenie B

?: istnieje kolejność wykonywania zadań, tak, aby zakończyły się przed czasem B

• Programowanie całkowitoliczbowe, (ale programowanie liniowe

jest w P, chociaż praktycznie stosowany algorytm sympleks jest wykładniczy)

• Pakowanie

Jak jest minimalna liczba pudełek o ustalonej pojemności, które pomieszczą zbiór elementów o zadanych rozmiarach.

• Pakowanie 2-wymiarowe

minimalna długość paska materiału potrzebna do wycięcia zadanych kształtów.

Ważne problemy podejrzewane o to, że są pośrednie:

• Izomorfizm grafów

• Liczby pierwsze

• Liczby złożone

Zakładana trudność obliczeniowa dwóch ostatnich jest podstawą współczesnej kryptografii.

(Nieliczne) problemy, dla których wykazano trudność obliczeniową (tzn. że na pewno wymagają czasu wykładniczego):

1. Szachy, warcaby (uogólnione, N x N), inne gry (problem istnienia strategii wygrywającej w danej konfiguracji)

2. problemy z logiki matematycznej

3. problemy z teorii języków formalnych

Metody pokonywania problemu trudnego obliczeniowo

dotyczą wersji optymalizacyjnych (np. szukanie minimum)

1. Dokładna analiza, być może jest łatwy, bo ograniczony do szczególnego rodzaju instancji

(np. kolorowanie, gdy graf nie ma cykli, jest bardzo łatwe, a sprawdzenie tego też jest łatwe)

2. Heurystyki szukające optimum, redukujące specjalnymi technikami czas obliczeń (często nieskutecznie), np.

metoda rozgałęzień i ograniczeń ('branch & bound')

3. Algorytmy (albo: strategie) aproksymacyjne :

czas szybki, wynik poprawny ale niedokładny, z gwarancją ograniczenia wielkości błędu, postaci

A(I) <= c OPT (I), dla każdej instancji I

A(I) - wielkość (koszt) wyniku algorytmu aproksymacyjnego

c - stała, niezależna od instancji, na pewno większa niż 1

(dla problemu maksymalizacyjnego nierówność odwrotna).

Np. Strategia "2MST"

TSP, z nierównością trójkąta (tzn. d(i,j) <= d(i,k) + d(k,j), ∀i,j,k ); (jest to, mimo ograniczenia, dalej problem NPC)

1. Znajdź minimalne drzewo rozpinające dla zbioru miast (traktowanego jako graf pełny).

2. Obejdź drzewo standardowa metodą przeglądu grafu, krawędzie trawersowane zarówno w przód jak i w tył wypisuj - utworzą cykl.

3. W tym cyklu usuń powtarzające się wierzchołki (dokonując skrótów) - powstanie cykl elementarny C, jest to wynik strategii.

Fakt: C <= 2 * OPT

Dowód: MST <= OPT, bo cykl komiwojażera, po rozcięciu jest ścieżką, czyli szczególnym przypadkiem drzewa rozpinającego.

Zatem cykl tworzony w kroku 2 ma długość <= 2*OPT.

Wykonanie skrótów, z nierówności trójkąta, nie wydłuża cyklu.

Poszukiwania strategii aproksymacyjnych

dla danego problemu trudnego obliczeniowo

Możliwe są 3 przypadki:

1. Nie istnieje strategia o powyższych własnościach (tzn. posiadająca skończoną stała c)

Np. TSP (bez ograniczeń). Tw.: Jeśli istnieje taka strategia, to HC jest łatwy, więc P=NP.

2. Istnieje taka strategia, np.

- dla problemu pokrycia wierzchołkowego istnieje prosta strategia o współczynniku 2, i prawdopodobnie nie ma lepszej.

- dla TSP z nierównością trójkąta istnieje strategia o współczynniku 1.5.

3. Istnieje rodzina strategii o współczynnikach dowolnie bliskich 1, np.

- dla problemu plecakowego

- dla TSP, gdy odległości jak w przestrzeni Euklidesowej

Literatura:

1. Harel: Algorytmika - Rzecz o istocie informatyki

2. Cormen, Leiserson, Rivest: Wprowadzenie do algorytmów

3. Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-completeness

4. Ausiello i in.: Complexity and Approximation - Combinatorial Optimization Problems and Their Approximability Properties

7

---