In the MAX SAT problem, we are given a set of clauses, and we want to find an assignment t...

In the MAX SAT problem, we are given a set of clauses, and we want to find an assignment that satisfies as many of them as possible.

(a) show that if this problem can be solved in polynomial time, then so can SAT.

---

(b) Here’s a very naive algorithm.

 for each variable:
  set its value to either 0 or 1 by flipping a coin

Suppose the input has m clauses, of which the jth has kj literals. Show that the expected number of clauses satisfied by this simple algorithm is

In other words, this is a 2-approximation in expectation! And if the clauses all contain k literals, then this approximation factor improves to 1 + 1/(2k– 1).

---

(c) Can you make this algorithm deterministic? (Hint: Instead of flipping a coin for each variable, select the value that satisfies the most as-yet-unsatisfied clauses. What fraction of the clauses is satisfied in the end?)