Consider a special version of 3-SAT that requires that each variable has exactly 3 occurrences, but allows each clause to have either 2 or 3 literals. Let's call this problem 2,3-SAT3. Here is an example of an instance of 2,3-SAT3 problem: (x1 V2 V3) A (1V 2V 4) A (x1 V4) A (2 VT3) A (x3 V14) Note that each variable has exactly 3 occurrences. We want to show that 2,3-SAT3 is NP-hard. Follow the following steps to reduce 3-SAT to 2,3-SAT3 For simplicity, you may assume that in each instance of 3-SAT, every variable has at least 2 occurrences. (a) Given variables y1, y2,..., Yk, k > 2, design a set of 2-literal clauses such that there are exactly two assignments for these variables that satisfy the set of your designed clauses: (i) y = y2 = ... = Yk = false, and (ii) y = Y2 = ... = Yk = true. Each variable should have exactly 2 occurrences in these clauses. (b) Now consider an instance S of 3-SAT in which variable x; has k 2 occurrences. Using part (a) construct a new instance S' by replacing all occurrences of x; with new variables y1,..., yk. Add necessary clauses to make the original instance S and the new instance S' equivalent (one is satisfiable if and only if the other is satisfiable). Argue why each of these new variables has exactly 3 occurrences in S'. (c) Describe a reduction from 3-SAT to 2,3-SAT3 as an algorithm. (d) Prove correctness of your reduction! Bonus. Describe a reduction from 3-SAT to 2,3-SAT3 without assuming the simplifying assumption (that each variable in 3-SAT instance has at least 2 occurrences). Activ