(Solved): (More on the power of linearity of expectation) Recall the Max-SAT problem. The input is a Boolean ...

(More on the power of linearity of expectation) Recall the Max-SAT problem. The input is a Boolean formula in conjunctive normal form and you wish to output an assignment of the variables that satisfy the maximum number of clauses. This problem is (famously) known to be NP-hard. (a) Show that a random assignment of the variables satisfies at least $$50\%$$ of the optimal number of true clauses in expectation. Hint: consider a r.v. for each clause denoting whether the corresponding clause evaluates to true. (b) Consider an input of MAX-Exact-3SAT (now every clause is the disjunction of exactly three literals). Slightly refine your analysis from part (a) to conclude that a random assignment will satisfy at least $$87.5\%$$ of the clauses in expectation. (c) Show that for MAX-Exact-3SAT, if there is an assignment that satisfies strictly less than $$87.5\%$$ of the clauses, then there is another assignment that satisfies strictly more than $$87.5\%$$ of the clauses. Hint: there is an elegant and important proof that follows from the formula of expectation and your result from part (b). (d) Give an example of an input of MAX-Exact-3SAT such that every assignment satisfies exactly $$87.5\%$$ of the clauses. Hint: $$2^3=8$$.