3. Consider the problem LPS defined as follows: "Given a matrix A Rnxn, a vector b E Rn and an integer k >0, does there exist a vector r E R" with at most k non-zero entries such that A b". Here A x denotes the usual matrix-vector product and for two vectors u, v, we say u2v if for every i, uii Give a polynomial-time reduction from 3SAT to LPS. 75 points) (Hint: Use the reductions done in class along-with transitivity of Sp to first pick the "right" starting point and then design a reduction from this starting point.)