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?

$\endgroup$
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$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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