(7 points) Reduction from 3-SAT to Subset Sum.

(1) Using 3-SAT input:

A1 = (x1 x2 x3), A2 = (x1 x4 x3), A3 = (x1 x2 x3), write down the corresponding instance of Subset Sum that is built when following the reduction procedure. Note you will be creating a Subset Sum instance, which is a set of integers and a target sum W, from the 3-SAT input.

(b) Show how a subset of the integers you created that sums to the target sum W corresponds to a satisfying assignment of all k = 3 clauses.