1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Hint: You have a 3SAT formula $\varphi$ in CNF with $n$ clauses and a maximal $m \le n$ number of clauses can be satisfied. What happens if $m < n$? And what about $m = n$?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.