Max-SAT is NP-hard

Statement

Lemma

Max-SAT is NP-hard

Proof

There is a many-one reduction from the SAT problem to max-SAT.

If we have an instance of the SAT problem plug it into max-SAT and if we get an assignment the satisfies all clauses return that, otherwise say no.

As SAT is NP-complete this gives that max-SAT is NP-hard.