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

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

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

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

wprowadzana jest kwadratowa liczba nowych zmiennych Źle

wprowadzana jest liniowa liczba nowych zmiennych Dobrze

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

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

działa w czasie wielomianowym Źle

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

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

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

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 Dobrze

$3m$ krawędzi Źle

$3n$ wierzchołków Źle

$3m+2n$ krawędzi Źle

co najmniej $3m$ krawędzi Dobrze

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 Źle

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

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

Z tego powodu zmniejsza się liczbę selektorów Źle

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

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

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

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

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

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 Źle

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

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

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

zbiór trójek ma $\Theta (n^{2}+m)$ elementów Źle

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 Dobrze

reprezentują moce podzbiorów Źle

są wielkości wielomianowej od $m$ i $n$ Źle

są zapisane na $O(m+n)$ bitach Dobrze

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