3
$\begingroup$

I've been reading this article which tries and explains how the max 2 sat problem is essentially a 3-sat problem and is NP-hard.

However, if you see the article, I'm not able to understand why, after ci is satisfied, 7 out of 10 clauses are satisfied and if it is not satisfied, the 6 out of 10 clauses are satisfied.

Can someone explain to me in simple terms, and demystify what exactly the article wants to convey? Essentially, I have come to know that a max-2-sat problem is the same as a 3 sat problem. The question is I'm not able to understand why.

More formally, I wish to solve this problem:

Consider the problem MAX2SAT described as follows.

Given a 2-CNF (Conjunctive Normal Form) Boolean expression (with m clauses, n variables) and an integer k, Decide if there is an assignment satisfying at least ‘k’ of the total clauses? Compute the complexity class (P or NP or NP Complete) of the MAX2SAT with justification.

Improve this question
$\endgroup$
5

1 Answer 1

Reset to default
3
$\begingroup$

It seems that the lecture note has abused the symbol $c_i$. You should check the original paper.

Replacing each clause $C_i = (a_i \lor b_i \lor c_i)$ of 3CNF by the collection of 2CNF clauses:

$$(a_i), (b_i), (c_i), (d_i), (\bar{a_i} \lor \bar{b_i}), (\bar{a_i} \lor \bar{c_i}), (\bar{b_i} \lor \bar{c_i}), (a_i \lor \bar{d_i}), (b_i \lor \bar{d_i}), (c_i \lor \bar{d_i})$$

where $d_i$ is a new variable.

Theorem: If an assignment $\alpha$ satisfies $C_i$, then exactly seven of the ten clauses in the 2-CNF collection can be satisfied.

Proof: $\alpha$ satisfies $C_i$, then either one, two, or three of $a_i, b_i, c_i$ must be true. In all cases, there is a truth setting for $d_i$ causing exactly seven of the clauses to be satisfied. For example, suppose $a_i = \top, b_i = c_i = \bot$, then $d_i = \bot$ causes 7 clauses to be satisfied.

Theorem: If an assignment $\alpha$ does not satisfy $C_i$, then exactly six of the ten clauses can be satisfied.

Proof: $\alpha$ does not satisfy $C_i$, then $a_i = b_i = c_i = \bot$. In this case, if $d_i = \top$, 4 clauses are satisfied; if $d_i = \bot$, then 6 clauses are satisfied.

Improve this answer
$\endgroup$
4
  • $\begingroup$ "di" is a new variable. Cool but is a 3 sat problem, we only have a,b,c (3 variables basically) correct? What EXACTLY is di? $\endgroup$
    – gabbar0x
    Commented Jan 30, 2016 at 11:59
  • $\begingroup$ @bholagabbar 3 means "each clause contains at most three literals". No limitation to the number of variables used in a formula. Note that $(d_i)$ means a single 2CNF clause. $\endgroup$
    – hengxin
    Commented Jan 30, 2016 at 12:03
  • $\begingroup$ Ok..and how do we finally conclude that this is NP? I mean what justification do we give formally? $\endgroup$
    – gabbar0x
    Commented Jan 30, 2016 at 12:06
  • 3
    $\begingroup$ @bholagabbar NP or NP-hard? For NP, you prove that you can verify whether an assignment of an Max-2CNF formula is a valid one in polynomial time. This is an easy part. For NP-hard, you can set $k = 7m/10$ combine the two theorems together and conclude that (in the lecture note): "If $F$ of 3CNF is satisfiable then there is an assignment satisfying 7/10 of the clauses in $F′$ of 2CNF, and if $F$ is not satisfiable then no assignment satisfies 7/10 of the clauses in $F'$". $\endgroup$
    – hengxin
    Commented Jan 30, 2016 at 12:16

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.