Zamknięte

Question 1

Załóżmy że P nierówne NP. Mówimy, że A jest pełny dla każdej liczby n zachodzi, że:
język A albo nie zawiera żadnego słowa długości n albo zawiera wszystkie takie słowa. Co można powiedzieć o złożoności pełnego języka należącego do NP?

Answer 1

na pewno nie jest NP-zupełny

Question 2

Która z poniższych klas zawiera wszystkie pozostałe (zakładając że hierarchia wielomianowa jest nieskończona)

Answer 2

NP^NP

Question 3

Który z problemów redukuje się w czasie wielomianowym do problemu stwierdzenia czy graf G posiada podgrzać pełny zadanego rozmiaru k

Answer 3

każdy: problem stwierdzenia czy G ma zbiór wierzchołków niezależnych k, czy dana formuła rachunku zdań jest spełnialna i stwierdzenia czy G posiada cykl Hamiltona

Question 4

który z poniższych wariantów problemu SAT CNF jest NP-zupełny

Answer 4

każda klauzula zawiera najwyżej 3 literały

Question 5

Załóżmy że P nie równa się NP. Pewien język A należy do NP. Co można o nim powiedzieć?

Answer 5

(żadne z: A jest NP zupełny, A jest NP trudny, A należy do P lub jest NP zupełny)

Question 6

Rozważamy pewien NP zupełny język A. Co można powiedzieć o A?

Answer 6

na pewno należy do NP ale nie musi być NP zupełny (ale nie da się można tego wykluczyć)