Decision vs. Optimization

[5 marks] SATISFIABILITY. In class we have seen the NP-complete problem 3-SAT. where each clause has 3 literals. Recall that a literal is a variable x or the negation of a variable Tp The variant where each clause has at most 2 literals is solvable in polynomial time. However, the following problem is NP-complete: MAX 2-SAT. Input: a number k0, a set of n Boolean variables, i,, .. Tn and a set C of m clauses, where each clause has the form (V) where l and lj are literals. Question: is there an assignment of truth-values to the variables that makes at least k of the clauses true? Suppose you have a polynomial time algorithm for the above MAX 2-SAT decision problem. Show that you can use this algorithm to find the maximum number of clauses that can be made true, and to find a truth-value assignment that satisfies that number of clauses, both in polynomial time. [5 marks] SATISFIABILITY. In class we have seen the NP-complete problem 3-SAT. where each clause has 3 literals. Recall that a literal is a variable x or the negation of a variable Tp The variant where each clause has at most 2 literals is solvable in polynomial time. However, the following problem is NP-complete: MAX 2-SAT. Input: a number k0, a set of n Boolean variables, i,, .. Tn and a set C of m clauses, where each clause has the form (V) where l and lj are literals. Question: is there an assignment of truth-values to the variables that makes at least k of the clauses true? Suppose you have a polynomial time algorithm for the above MAX 2-SAT decision problem. Show that you can use this algorithm to find the maximum number of clauses that can be made true, and to find a truth-value assignment that satisfies that number of clauses, both in polynomial time