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

From Studia Informatyczne

W przedstawionym dowodzie NP-zupełności problemu 3SAT

klauzula k-składnikowa zastępowana jest przez k-2 klauzul

klauzula k-składnikowa zastępowana jest przez 2 klauzule

wprowadzana jest kwadratowa liczba nowych zmiennych

wprowadzana jest liniowa liczba nowych zmiennych

klauzule o mniej niż 4 składnikach pozostają bez zmian


Przedstawiona redukcja dowodząca, że MAX2SAT jest problemem NP-zupełnym, jest redukcją logarytmiczną, gdyż

działa w czasie wielomianowym

rozmiar wyniku redukcji jest wielomianowy od długości formuły wejściowej

rozmiar wyniku redukcji można zapisać w pamięci O(\log n)

istnieje realizujący ją algorytm (maszyna Turinga) używający logarytmicznej pamięci roboczej


Na wejściu redukcji dowodzącej, że problem NODE COVER jest NP-zupełny, dana jest formuła o m klauzulach nad n zmiennymi. W utworzonym grafie jest

3m wierzchołków

3m krawędzi

3n wierzchołków

3m+2n krawędzi

co najmniej 3m krawędzi


W jaki sposób w dowodzie NP-zupełności problemu HAMILONIAN CYCLE korzysta się z tego, że gadżet można trawersować dwukrotnie, za każdym razem inną połowę gadżetu?

Konstruując pokrycie, możemy wykorzystać dwukrotne trawersowanie gadżetu

Przy konstrukcji cyklu w gadżecie, pozwala to uwzględnić sytuację, gdy oba końce krawędzi są w pokryciu

Z tego powodu zwiększa się liczbę selektorów

Z tego powodu zmniejsza się liczbę selektorów


Problem HAMILTONIAN PATH, należący do klasy NP,

jest zacieśnienieniem problemu HAMILTONIAN CYCLE i dlatego jest NP-zupełny

jest uogólnieniem problemu HAMILTONIAN CYCLE i dlatego jest NP-zupełny

to problem o takiej samej dziedzinie jak HAMILTONIAN CYCLE i dlatego jest NP-zupełny

to problem różny od HAMILTONIAN CYCLE, więc wymaga osobnego dowodu NP-zupełności


Jeśli na wejściu redukcji z problemu 3SAT do TRIPARTITE MATCHING dana jest formuła składająca się z m klauzul nad n zmiennymi, to na wyjściu

zbiory W, X, Y mają po m+n elementów

zbiory W, X, Y mają po 2nm elementów

zbiór trójek ma 2mn+3n elementów

zbiór trójek ma \Theta(m^2n) elementów

zbiór trójek ma \Theta(n^2+m) elementów


W redukcji dowodzącej NP-zupełności problemu SUBSET SUM, niech zbiór wejściowy ma moc 3m, a zbiór trójek n. Na wyjściu redukcji otrzymane liczby

reprezentują podzbiory trójelementowe

reprezentują moce podzbiorów

są wielkości wielomianowej od m i n

są zapisane na O(m+n) bitach

są zapisane na O(\log m+\log n) bitach