7 Extra Credit (5 points) In normal 3-SAT, a satisfying assignment of variables is an assignment where each clause has at least one of its variables satisfied. So in a satisfying assignment of an instance of 3-SAT, each clause is satisfied by 1, 2, or 3 of its variables. Consider the problem PARTIAL SAT, which is like 3-SAT, except clauses are not allowed to have all of their variables satisfied they must all be satisfied by 1 or 2 of their variables For example, consider (r1 Vac2 V-T3) A (-r1 V r2 V-as). If we take that as an instance of 3SAT, setting T1 and T3 to false, and a2 to true, would satisfy it. However, that would not be a valid solution to the instance of PARTIAL SAT, since all 3 variables in the second clause are satisfied by that truth assignment. Setting 1 and T2 to true, and z3 to false, however, would solve the instance of PARTIAL SAT, since the first clause is satisfied by 2 variables and the second clause is satisfied by 1 variable. Prove that PARTIAL SAT is NP-complete. (Hint: reduce from -SAT; for each clause in the original instance of 3-SAT, make 2 clauses in PARTIAL SAT using some new variables) 7 Extra Credit (5 points) In normal 3-SAT, a satisfying assignment of variables is an assignment where each clause has at least one of its variables satisfied. So in a satisfying assignment of an instance of 3-SAT, each clause is satisfied by 1, 2, or 3 of its variables. Consider the problem PARTIAL SAT, which is like 3-SAT, except clauses are not allowed to have all of their variables satisfied they must all be satisfied by 1 or 2 of their variables For example, consider (r1 Vac2 V-T3) A (-r1 V r2 V-as). If we take that as an instance of 3SAT, setting T1 and T3 to false, and a2 to true, would satisfy it. However, that would not be a valid solution to the instance of PARTIAL SAT, since all 3 variables in the second clause are satisfied by that truth assignment. Setting 1 and T2 to true, and z3 to false, however, would solve the instance of PARTIAL SAT, since the first clause is satisfied by 2 variables and the second clause is satisfied by 1 variable. Prove that PARTIAL SAT is NP-complete. (Hint: reduce from -SAT; for each clause in the original instance of 3-SAT, make 2 clauses in PARTIAL SAT using some new variables)