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

Problem 2SAT sprowadza się do

sortowania topologicznego grafu Źle

znajdowania składowych grafu Źle

znajdowania dwuspójnych składowych grafu Źle

testowania acykliczności grafu Źle

żadna z pozostałych odpowiedzi nie jest poprawna Dobrze

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

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

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

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

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

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

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 Dobrze

$\Theta (m+k)$ krawędzi Dobrze

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

$\Theta (n+k^{2})$ wierzchołków Źle

$\Theta (m+k^{2})$ krawędzi Źle

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

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

o złożoności na przykład $n^{\log }n$ Źle

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

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

Problem silnie NP-zupełny, to

na przykład, EXACT COVER BY 3SETS Dobrze

na przykład, SUBSET SUM Źle

każdy nieliczbowy problem NP-zupełny Dobrze

każdy liczbowy problem NP-zupełny Źle

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

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 Dobrze

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

wskazać algorytm pseudowielomianowy dla tego problemu Źle

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

Problem 3OCCUR 3SAT

nie jest podproblemem problemu 3SAT Źle

nie jest silnie NP-zupełny Źle

jest NP-zupełny Dobrze

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