Zk 13.2.2012
Napsal: 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
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