(4) (20 points) In this problem, we want to show that properly PAC-learning monotone k-sparse disjunctions is NP-hard, by reducing from Set Cover. To this end, give a polynomial-time reduction from Set Cover to the following problem: Sparse Monotone Disjunction Input: labelled samples (x1,y1),,(xm,ym) where xi{0,1}r and yi{0,1} Goal: Find sparsest monotone disjunction h consistent with all labels, i.e. h(xi)=yi for 1im Sparsest means h involves as few literals as possible