Prove that each of following problems: Show that it is in NP by sketching a polynomial time verifier for it. Show that each problem is NP-hard by giving a polynomial time reduction from a known NP-complete problem to the one in question. (1) TWO SOLUTIONS = {(F) | F is a boolean formula which is satisfied by two different assignments of truth values to your variables} (2) LPATH = {(G, s, t, k) | G is an undirected graph with a simple path from s to t with length at least k} (3) HALF-SUBSET = (S, t) | S = {x_1, .... x_n} is a set of positive numbers such there exists a set {y_1, ... y_k} dubsetoforequalto S where sigma^k_i=1 y_i = t and k lessthanorequalto n/2 (i.e., we use less than half the numbers in S to get t)}