= 2 2 2 2 = Let 3DIV = { S is a set of positive integers and S can be partitioned into 3 subsets all having the same sum } For example {1, 2, 3, 6, 8, 9, 10, 12 } E 3DIV because 2 + 3 + 12 = 8 +9=1 + 6 + 10 = 17 Prove that 3DIV is NP-complete. [You can use the fact that PSS, which is the SUBSET-SUM problem with all positive integers is NP-complete: PSS = { | W = {x1, X2, Xx} where all x;> 0 and for some {y, Y2, yi} = {X1, X2, ..., Xx}, we have Ey; = t}.] = 2 ... = 2 2 2 2 = Let 3DIV = { S is a set of positive integers and S can be partitioned into 3 subsets all having the same sum } For example {1, 2, 3, 6, 8, 9, 10, 12 } E 3DIV because 2 + 3 + 12 = 8 +9=1 + 6 + 10 = 17 Prove that 3DIV is NP-complete. [You can use the fact that PSS, which is the SUBSET-SUM problem with all positive integers is NP-complete: PSS = { | W = {x1, X2, Xx} where all x;> 0 and for some {y, Y2, yi} = {X1, X2, ..., Xx}, we have Ey; = t}.] = 2