(15+5%) Consider the problem MAJORITY-SAT: Given a boolean expression F with n variables, is it true for more than half of the 2" valuations of its variables? (a) Prove that BOOL-SAT p MAJORITY-SAT [Hint: conjunct the input expression with a fresh variable.] (b) MAJORITY-SAT is not NP-complete. Why? What's the problem? (15+5%) Consider the problem MAJORITY-SAT: Given a boolean expression F with n variables, is it true for more than half of the 2" valuations of its variables? (a) Prove that BOOL-SAT p MAJORITY-SAT [Hint: conjunct the input expression with a fresh variable.] (b) MAJORITY-SAT is not NP-complete. Why? What's the