Subset sum → Dělení kořisti

Problémy subset sum a dělení kořisti (partition problem) jsou NP-úplné kombinatorické úlohy. Pokud bychom pouze věděli, že je problém subset sum NP-úplný, ale o problému dělení kořisti tuto informaci neměli, tak tento převod dokazuje NP-úplnost problému dělení kořisti (pro úplnost je zapotřebí ukázat, že je dělení kořisti v NP, což je ale zřejmé, jelikož ANO-instanci lze ověřit v polynomiálním čase posčítáním cen položek v jednotlivých podmnožinách).

Subset sum

Je dána množina přirozených čísel M = \\{n_{1}, n_{2}, \\cdots, n_{r}\\} a číslo k. Rozhodovací problém se ptá, zda-li lze vybrat z M pomnožinu N tak, že součet čísel z N je roven k.

Dělení kořisti

Je dána množina přirozených čísel M = \\{n_{1}, n_{2}, \\cdots, n_{r}\\}. Rozhodovací problém se ptá, zda-li lze tuto množinu rozdělit na dvě podmnožiny tak, že součet čísel v nich obsažených bude totožný.

Převod

Protože máme rozdělit na dvě stejné části jednu množinu M, tak aby se z nich dalo usoudit na číslo k, musíme do množiny M přidat právě jeden další pomocný předmět, který jednu z podmnožin dováží na požadovanou mez.

Pokud označíme součet váhy všech předmětů A, pak mohou nastat dvě situace. Buď platí 2k \\leq A nebo 2k \\gt A.

2k ≤ A

Pokud platí 2k \\leq A, pak přidáme do M předmět o váze A - 2k. Tuto váhu jsme zvolili podle následující logiky. V obou podmnožinách má být stejný součet hodnot. Protože platí uvedená nerovnost, pak v každé z těchto podmnožin může být umístěn náklad o hmotnosti k a polovina zbytku nákladu do A. Takto by šel náklad vyskládat pouze za podmínky možnosti dělení předmětů. Proto pokud z první podmnožiny přesuneme zbytek nákladu nad mez k do druhé podmnožiny, tak je v druhé podmnožině naloženo náklad o hmotnosti k + A - 2k (zatímco v té první pouze k). První množinu proto dovážíme přidaným předmětem o zmíněné hmotnosti (zároveň je zřejmé, že k žádnému dělení nákladu již nedochází).

Všimněme si, že nám tento převod dává také postup, jak z řešení problému dělení kořisti získat řešení subset sum problému. Stačí z té podmnožiny, která obsahuje přidaný předmět, tento předmět odebrat a zbytek nákladu je řešením subset sum. Zároveň je vidět, že tato konstrukce je možná tehdy a jen tehdy, pokud původní problém subset sum obsahuje řešení. Z opačné strany platí, že pokud má takto konstruovaný problém dělení kořisti řešení, pak musí existovat odpovídající subset sum problém.

2k > A

Druhou situací je, pokud platí 2k \\gt A. V tento okamžik bychom chtěli, abychom měli dvě podmnožiny váhy přesně k. První podmnožina bude odpovídat řešení problému subset sum a druhá bude obsahovat zbytek do A a přidaný předmět o váze 2k - A.

I tento převod je proveditelný jen tehdy, pokud si ANO-instance problémů vzájemně odpovídají.

Složitost převodu

Jelikož je úloha modifikována pouze přidáním jednoho předmětu, tak je tento převod zjevně polynomiální.








Doporučujeme

Internet pro vaši firmu na míru

Pořiďte si internet na doma ještě dnes