Consider a 3-CNF formula ? containing m clauses. We say that ? is K-satisfiable if there is an assignment that makes at least K of the clauses of ? true. Note that K may be smaller than m, so this is a weaker notion than ordinary satisfiability Consider the following language: to the variables of ? MAXSAT-t(?, K) I ? is a 3-SAT formula that is K-satisfiable} Prove carefully that the language MAXSAT is NP-complete. You may use any NP- completeness result covered in class (CKTSAT, SAT, 3-SAT, CLIQUE) but no other. Consider a 3-CNF formula ? containing m clauses. We say that ? is K-satisfiable if there is an assignment that makes at least K of the clauses of ? true. Note that K may be smaller than m, so this is a weaker notion than ordinary satisfiability Consider the following language: to the variables of ? MAXSAT-t(?, K) I ? is a 3-SAT formula that is K-satisfiable} Prove carefully that the language MAXSAT is NP-complete. You may use any NP- completeness result covered in class (CKTSAT, SAT, 3-SAT, CLIQUE) but no other