2) Ukažte, že problém Omezený součet podmnožiny je polynomiálně řešitelný:
Instance: Množina n prvků
Otázka: Existuje množina prvků
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