The 3-dimensional matching (3DM) problem is given as follows: Given three disjoint q-element sets X,Y,Z and a subset of ordered 3-tuples M in (XYZ), the problem is to determine whether there is a subset QM such that each element in XYZ belongs to exactly one member of Q. If such a subset Q exists, then Q=q and we call Q a. 3-dimensional matching of M. See this link for more information on 3-dimensional matching. In this question, we assume that the 3-dimensional matching problem is NPComplete. Now consider the following problem which we will call the intersection numbers problem where an instance is given by - a finite set A of size n, - a collection of m subsets B1,B2,,Bm of A, and - m non-negative (not necessarily distinct) integers t1,t2,,tm. The intersection numbers problem is to decide if there is a subset WA such that for each i=1,2,,m, WBi=ti. The goal of this question and question 2 is to show that the intersection numbers problem is NPComplete. To help with this, consider the following mapping of instance of the 3DM problem to an instance of the intersection numbers problem. Let X,Y,Z be three disjoint sets of cardinality q and suppose M={M1,M2,,Mm}XYZ. This constitutes an instance of 3 -dimensional matching problem. We now construct an instance of the intersection numbers problem as follows: Let A={1,2,3,,m}. We construct set Bi for each member iXYZ where the value j is placed into Bi if and only if iMj. This constructs a total of 3q sets. We set ti=1 for each iXYZ. This completes our construction of the intersection numbers problem instance. Example: Consider the 3DM problem instance given by X={1,2,3},Y={4,5,6},Z={7,8,9} (so q=3) and the ordered-triples M1=(1,4,7),M2=(1,4,8),M3=(2,5,8),M4=(2,6,7),M5=(3,6,9), M6=(3,6,7),M7=(3,5,8)( so m=7). The constructed instance of the intersection numbers instance is: A={1,2,3,4,5,6,7},B1={1,2},B2= {3,4},B3={5,6,7},B4={1,2},B5={3,7},B6={4,5,6},B7={1,4,6},B8={2,3,7},B9={5} and t1=1, for i=1 to 9 Answer the following questions: (a) Show that the construction can be done in polynomial time. (b) Show that if the 3DM problem instance is a yes-instance, then the constructed instance of the intersection numbers problem is also a yes-instance