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

From Studia Informatyczne

Problem 2SAT sprowadza się do

sortowania topologicznego grafu

znajdowania składowych grafu

znajdowania dwuspójnych składowych grafu

testowania acykliczności grafu

żadna z pozostałych odpowiedzi nie jest poprawna


Problem kolorowania, w którym dodatkowo założymy, że

stopień każdego wierzchołka jest ograniczony przez 3, jest NP-zupełny

stopień każdego wierzchołka jest ograniczony przez 4, jest NP-zupełny

liczba kolorów jest ograniczona przez 3, jest NP-zupełny

liczba kolorów jest ograniczona przez 3 oraz graf jest planarny, jest NP-zupełny

stopień każdego wierzchołka jest ograniczony przez 4 oraz graf jest planarny, jest NP-zupełny


W redukcji z problemu kolorowania grafu o n wierzchołkach i m krawędziach do problemu kolorowania grafu planarnego, po narysowaniu grafu wejściowego na płaszczyźnie otrzymano k przecięć krawędzi. Graf planarny będący wynikiem redukcji ma

\Theta(n+k) wierzchołków

\Theta(m+k) krawędzi

\Theta(n+mk) wierzchołków

\Theta(n+k^2) wierzchołków

\Theta(m+k^2) krawędzi


W terminach problemów algorytmicznych, pseudowielomianowym nazywamy algorytm, który jest

wielomianowy jeśli liczby są zapisane przy podstawie 2, wykładniczy jeśli liczby są zapisane unarnie

wielomianowy jeśli liczby są zapisane unarnie, wykładniczy jeśli liczby są zapisane przy podstawie 2

o złożoności na przykład n^\log n }

wykładniczy od rozmiaru danych i wielomianowy od wartości liczb w instancji

wielomianowy od rozmiaru danych i wykładniczy od wartości liczb w instancji


Problem silnie NP-zupełny, to

na przykład, EXACT COVER BY 3SETS

na przykład, SUBSET SUM

każdy nieliczbowy problem NP-zupełny

każdy liczbowy problem NP-zupełny

problem, w którym nawet przy kodowaniu unarnym zachowana jest NP-zupełność


Aby wykazać, że problem jest silnie NP-zupełny, wystarczy

wykazać, że posiada NP-zupełny podproblem o wielomianowo ograniczonej wartości największej liczby w instancji

skonstruować redukcję wielomianową z silnie NP-zupełnego problemu

wskazać algorytm pseudowielomianowy dla tego problemu

wykazać, że jest podproblemem silnie NP-zupełnego problemu


Problem 3OCCUR 3SAT

nie jest podproblemem problemu 3SAT

nie jest silnie NP-zupełny

jest NP-zupełny

jest NP-zupełny, nawet jeśli założymy, że każda klauzula zawiera 3 literały nad różnymi zmiennymi