(7 points) Hardness and Approximation of Maximum 2-SAT Consider a 2-SAT instance: there are n Boolean variables x... Tn and m clauses, each of the form of where l, could be xr or -xr for some variable xr The goal of maximum 2-SAT is to find an assignment to the xrs that satisfies the maximum number of these clauses (a) (1 points) Give a decision version of maximum 2-SAT. (b) (3 points) We will show that maximum 2-SAT is NP-complete by showing that MAX-CUT MAX-2-SAT Here MAX-2-SAT is the decision version of the maximum 2-SAT problem that you defined in part a). The definition of the deterministic version of MAX-CuT (which you may assume is NP-complete) is Definition 0.1 (Decision Version of Max-Cut). Given an undirected unweighted graph G and a parameter k, answer whether there is a cut SC V(G) so that the number of edges leaving S is at least k. HINT: first figure out the following reduction involving a single edge: for two Boolean variables x and y, give two SAT clauses over them so that they are both satisfied when y, and only one of them is satisfied when x-y. (c) (1 points) Conclude from parts a) and b) that MAx-2-SAT is NP-Complete. (d) (2 points) Give a 2-approximation algorithm for the optimization version of maximum 2- SAT. Your algorithm should run in O(m) time