od wladik » 13. 2. 2012 19:11
1) Rozhodnout jestli množina
je rekurzivní, pokud není, tak jestli
nebo
je rekurzivně spočetná.
2) Ukažte, že problém Omezený součet podmnožiny je polynomiálně řešitelný:
Instance: Množina n prvků
, s každým prvkem
asociovaná velikost
, číslo
.
Otázka: Existuje množina prvků
pro níž platí, že:
3) NP-úplnost problému Set Packing
Instance: Množina C konečných množin a přirozené číslo
Otázka: Obsahuje C alespoň k po dvou disjunktních množin?
náznaky pro řešení:
1) Riceova věta tady nejde použít, jde o množinu trojic
2) Převodem na batoh
3) pomocí 3DM
1) Rozhodnout jestli množina [latex]S = \{ <x,y,z> | \varphi_x(z) \downarrow \wedge \varphi_y(z) \downarrow \wedge \varphi_x(z) = \varphi_y(z) \}[/latex] je rekurzivní, pokud není, tak jestli [latex]S[/latex] nebo [latex]\overline{S}[/latex] je rekurzivně spočetná.
2) Ukažte, že problém Omezený součet podmnožiny je polynomiálně řešitelný:
Instance: Množina n prvků [latex]A[/latex], s každým prvkem [latex]a \in A[/latex] asociovaná velikost [latex]v(a) \in \{ 0,...,n \}[/latex], číslo [latex]B \leq 0[/latex].
Otázka: Existuje množina prvků [latex]{A}' \subseteq A[/latex] pro níž platí, že:
[latex]\sum_{a\in{A}'}v(a)= B?[/latex]
3) NP-úplnost problému Set Packing
Instance: Množina C konečných množin a přirozené číslo [latex]k \leq 0[/latex]
Otázka: Obsahuje C alespoň k po dvou disjunktních množin?
náznaky pro řešení:
1) Riceova věta tady nejde použít, jde o množinu trojic
2) Převodem na batoh
3) pomocí 3DM