Max SAT MAX SAT is the following problem: Given a CNF formula and an integer g, find a truth assignment that satisfies at least g clauses. (It is guaranteed that g is no more than the number of clauses.) (1) Show that if we can solve MAX SAT in T(n.m) time, where n is the number of clauses and rn is the number of Boolean variables, then we can solve SAT in T(n,m) + O(n+ m) time (2) Show that MAX SAT Is in NP.