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í.