Złożoność obliczeniowa — NP-trudność i redukcje

Problemy decyzyjne vs optymalizacyjne

Teoria złożoności operuje na problemach decyzyjnych — pytaniach o odpowiedź TAK/NIE. Każdy problem optymalizacyjny można zamienić na odpowiadający mu problem decyzyjny:

Jeśli problem decyzyjny jest NP-trudny, to odpowiadający mu problem optymalizacyjny jest co najmniej tak samo trudny — nie może być łatwiejszy, bo mając algorytm optymalizacyjny moglibyśmy trivialnie rozwiązać problem decyzyjny.

Klasy złożoności

Klasa P

Zbiór wszystkich problemów decyzyjnych, które można rozwiązać w czasie wielomianowym względem rozmiaru wejścia:

\[ \text{P} = \{ L \mid \exists \text{ algorytm deterministyczny rozwiązujący } L \text{ w czasie } O(n^k) \} \]

Przykłady: sortowanie, najkrótsza ścieżka (Dijkstra), przepływ maksymalny.

Klasa NP

Nondeterministic Polynomial time — zbiór problemów decyzyjnych, dla których weryfikacja danego rozwiązania (świadka) może być wykonana w czasie wielomianowym:

\[ L \in \text{NP} \iff \exists \text{ wielomianowy algorytm weryfikacji} \; V: \; x \in L \Leftrightarrow \exists y: V(x,y) = 1 \]

Gdzie y to certyfikat (świadek). Przykład dla TSP: certyfikatem jest konkretna trasa — weryfikacja jej kosztu jest liniowa.

Otwarte pytanie P vs NP: Czy P = NP? Nie wiadomo — to jedno z siedmiu Problemów Milenijnych. Powszechnie przyjmuje się, że P ≠ NP.

Klasa co-NP

Problemy, których dopełnienie należy do NP — można efektywnie zweryfikować odpowiedź NIE. Przykład: dowód, że cykl Hamiltona NIE istnieje.

Relacje między klasami

P ⊆ NP ⊆ NP-zupełne ⊆ NP-trudne (przy założeniu P≠NP)

Redukcja wielomianowa

Definicja: Problem A jest wielomianowo redukowalny do problemu B (piszemy A ≤_p B), jeśli istnieje funkcja f obliczalna w czasie wielomianowym taka, że:

\[ x \in A \iff f(x) \in B \]

Intuicja: Jeśli umiemy rozwiązać B, to umiemy rozwiązać A — wystarczy przetransformować instancję A do instancji B, rozwiązać B i odczytać wynik. Redukcja mówi: "A nie jest trudniejszy od B".

Własności redukcji

• Jeśli A ≤_p B i B ∈ P, to A ∈ P
• Jeśli A ≤_p B i A ∉ P (przy P≠NP), to B ∉ P
• Redukcja jest przechodnia: jeśli A ≤_p B i B ≤_p C, to A ≤_p C

NP-zupełność

Problem L jest NP-zupełny, gdy:

1. L ∈ NP (można efektywnie weryfikować świadka)
2. ∀L' ∈ NP: L' ≤_p L (każdy problem z NP redukuje się do L — L jest "najtrudniejszy w NP")

Twierdzenie Cooka-Levina (1971)

SAT (spełnialność formuł logicznych) jest NP-zupełny. Każdy problem z NP można zredukować do SAT w czasie wielomianowym, bo każdy algorytm NP można zasymulować jako formułę logiczną.

Po udowodnieniu NP-zupełności SAT, kolejne problemy NP-zupełne udowadniamy przez redukcje z SAT lub z innych znanych problemów NP-zupełnych:

NP-trudność (NP-hard)

Problem L jest NP-trudny, gdy:

\[ \forall L' \in \text{NP}: L' \leq_p L \]

Każdy problem z NP redukuje się do L. Problem NP-trudny niekoniecznie musi należeć do NP (może być nawet trudniejszy — np. problemy PSPACE-trudne).

Jak udowodnić NP-trudność — schemat dowodu

Aby udowodnić, że problem X jest NP-trudny, stosujemy następujący schemat:

Częsty błąd: Redukcja musi iść od Y do X (nie od X do Y). Chcemy pokazać, że X jest co najmniej tak trudny jak Y — dlatego redukujemy znany trudny problem do naszego problemu X.

Przykład 1: 3-SAT ≤_p CLIQUE

Problemy

Konstrukcja redukcji

Dla formuły φ z m klauzulami tworzymy graf G:

1. Dla każdego literału w każdej klauzuli tworzymy wierzchołek (m klauzul × 3 literały = 3m wierzchołków)
2. Łączymy krawędzią wierzchołki (u_i, u_j) jeśli:
   • Należą do różnych klauzul
   • Ich literały nie są wzajemnie sprzeczne (nie są negacjami siebie)
3. Pytamy: czy G zawiera klikę rozmiaru k = m?

Poprawność

(⇒) Jeśli φ jest spełnialna (istnieje wartościowanie): wybieramy po jednym prawdziwym literale z każdej klauzuli — tworzą one klikę rozmiaru m (spełniony literał z każdej klauzuli, nie sprzeczne ze sobą).

(⇐) Jeśli G ma klikę rozmiaru m: klika ma dokładnie jeden wierzchołek z każdej klauzuli, literały nie są sprzeczne — możemy ustawić je na TRUE, co spełnia φ.

Przykład 2: PARTITION ≤_p KNAPSACK (0-1 KP jest NP-trudny)

Problemy

Konstrukcja redukcji

Dana instancja PARTITION: zbiór {a₁, …, aₙ}, suma S = Σaᵢ. Tworzymy instancję KNAPSACK:

• n elementów: element i ma wagę wᵢ = aᵢ i wartość vᵢ = aᵢ
• Pojemność plecaka W = S/2
• Pytamy: czy istnieje załadowanie o wartości V = S/2?

Poprawność

(⇒) Jeśli PARTITION ma rozwiązanie (podzbiór A o sumie S/2): wkładamy elementy A do plecaka — waga = S/2 ≤ W, wartość = S/2 = V. ✓

(⇐) Jeśli KNAPSACK ma rozwiązanie o wartości S/2: elementy w plecaku tworzą podzbiór sumy S/2, pozostałe też sumują się do S/2. ✓

Redukcja jest wielomianowa (liniowa). Ponieważ PARTITION jest NP-zupełny → 0-1 KP jest NP-trudny.

Przykład 3: Hamiltonowość ≤_p TSP (TSP jest NP-trudny)

Problemy

Konstrukcja redukcji

Dla grafu G = (V, E) tworzymy pełny graf ważony (instancję TSP):

• Wierzchołki: te same co w G
• Koszt krawędzi: c(i,j) = 0 jeśli (i,j) ∈ E, c(i,j) = 1 jeśli (i,j) ∉ E
• Próg: k = 0

Poprawność: G ma cykl Hamiltona ⟺ istnieje trasa TSP o koszcie 0 (korzysta tylko z krawędzi grafu G). Redukcja liniowa. Ponieważ HAM-CYCLE ∈ NP-zupełne → TSP jest NP-trudny.

Silna NP-trudność

Problem jest silnie NP-trudny, gdy pozostaje NP-trudny nawet gdy wszystkie liczby w instancji są ograniczone wielomianem rozmiaru wejścia (tzn. nie można go rozwiązać algorytmem pseudowielomianowym).

Algorytm pseudowielomianowy działa w czasie wielomianowym ze względu na rozmiar wejścia i wartości liczbowe w instancji (nie tylko rozmiar). Przykład: programowanie dynamiczne dla 0-1 KP działa w O(nV) — wielomianowe w n i V, ale V może być wykładniczo duże.

Klasy aproksymacji dla problemów NP-trudnych

Skoro nie znamy algorytmów wielomianowych dla problemów NP-trudnych, stosujemy:

Twierdzenie o nienaproksymowalności TSP

Jeśli P ≠ NP, to dla TSP ogólnego (asymetrycznego) nie istnieje algorytm aproksymacyjny o żadnej stałej gwarancji ρ. Dowód: gdyby istniał, rozwiązywałby HAM-CYCLE w czasie wielomianowym.

Dla TSP metrycznego (trójkąt nierówność): algorytm Christofidesa daje ρ = 3/2.

Podsumowanie — znane złożoności problemów PPD