I have the following problem:
Consider the MAX-3-SAT problem: given a Boolean function in Conjunctive Normal Form (CNF) determine the maximum number of clauses that can be satisfied. Prove that this problem is NP-hard.
I know that I'd have to reduce 3-SAT to MAX-3SAT, but I'm pretty lost on how that would work. The related decision problem I figured would be, given clauses and a number k, is there an assignment satisfying at least k of the clauses?