10. (7 points) In class we saw a in poly-time reduction from 3D Matching to Subset Sum. Recall that the 3D Matching problem gives you groups of three (aka "triples") to choose from, where each triple has one element from each of three different sets, X,Y, and Z, and then asks whether a subset M of the given triples T can be chosen so that each element of XYZ is in exactly one triple of M, thus forming a so-called "perfect 3D matching". 3D-matching p Subset Sum I.e., Subset Sum can solve the 3D-matching Problem Construction. Let XYZ be a instance of 3D-MATCHING with set T of triples. Let n=X=Y=Z and m=T. - Let X={x2,x2,x1,x4},Y={y1,y2,yy,y4},Z={z1,z2,zy,z4} - For each triple t=(x,y,zk)T, create an integer wt with digits that has a 1 in positions n+, and 2n+. Claim. There is a perfect 3D matching iff some subset sums to W= (a) Complete the blanlos in the figure/slide and table above to illistrate the reduction of the above 3D matching instance into at corresponding subset sum instance. (b) Say/ohow how a subset of the iategers you created that sums to the target sum W, corresponds to a subset MT that forms a perfect 3D matching