# Statement

# Proof

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

If we have an instance of the SAT problem , we submit it to max-SAT . If the resulting assignment satisfies all clauses, we return it; otherwise, we return no.

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