1
$\begingroup$

I'm trying to find reduction from 3-SAT to Max-2-SAT, so far no luck.
Let me first describe it.

3-SAT: Given a CNF formula $\varphi$, where every clause in $\varphi$ has exactly 3 literals in it, one should determine if there exist an assignment that satisfies it.

Max-2-SAT: Given a CNF formula, where every clause in $\phi$ has exactly 2 literals in it, and a positive number $k$, one should determine if there exist an assignment that satisfies at least $k$ clauses.

Let me first show what I have tried so far.
Given $\varphi=\wedge _{i=1}^{n}C_i$ where: $C_i=(l_{i_1}\vee l_{i_2} \vee l_{i_3})$,
I set: $\phi=\wedge _{j=1}^{3n}D_i$, where: $D_i=(l_{i_1}\vee l_{i_2})\wedge(l_{i_1}\vee l_{i_3})\wedge(l_{i_2}\vee l_{i_3})$ and $k=2n$.
It's quite easy to see that this will not work...
Although, if there exist an assignment which satisfies $\varphi$ it means there exist an assignment that satisfies $k=2n$ clauses in $\phi$, the second direction is not true.
I found several reductions online (such as this, for example), but none of them were useful since in my problem, each clause in $\phi$ must have exactly two literals, where in the link above, the formula can also contain 1-length clause in it.

I could really use some help here.

$\endgroup$
  • $\begingroup$ First-off, if you can have clauses of the form $\: x\lor x \:$ then this is trivial. $\;\;\;$ Are you allowed $\hspace{1.13 in}$ to have the same clause appear multiple times? $\;\;\;\;\;\;$ $\endgroup$ – user12859 Apr 12 '14 at 19:39
  • $\begingroup$ You know what? they didn't say anything about not using $x\vee x$... so I think I'll go with it. $\endgroup$ – so.very.tired Apr 12 '14 at 21:29
  • 1
    $\begingroup$ I don't think $x\lor x$ is legit. Otherwise it would be pointless to require that there be exactly two literals. $\endgroup$ – Yuval Filmus Apr 13 '14 at 23:02
1
$\begingroup$

Hint: Replace a singleton clause $a$ with $a \lor b$ and many copies of $\lnot b \lor c$, $\lnot b \lor \lnot c$.


Reductions without extra variables don't work even when singleton clauses are allowed. There are five types of clauses: $\ell_1,\lnot \ell_1, \ell_1 \lor \ell_2$, $\ell_1 \lor \lnot \ell_2$, $\lnot \ell_1 \lor \lnot \ell_2$. Suppose that $k$ of $\ell_1,\ell_2,\ell_2$ are true. The probability that a random clause of each type is true is: $$ \begin{array}{c|cccc} k&0&1&2&3\\\hline \ell_1 & 0 & 1/3 & 2/3 & 1 \\ \lnot \ell_1 & 1 & 2/3 & 1/3 & 0 \\ \ell_1 \lor \ell_2 & 0 & 2/3 & 1 & 1\\ \ell_1 \lor \lnot \ell_2 & 1 & 1/3 & 1/3 & 1\\ \lnot \ell_1 \lor \lnot \ell_2 & 1 & 1 & 2/3 & 0 \end{array} $$ We would like to take a convex combination of these rows which is of the form $$ \begin{array}{cccc} \alpha & \beta & \beta & \beta \end{array} $$ However, all such convex combinations have $\alpha = \beta$.

$\endgroup$
  • $\begingroup$ I just doubled every singleton. so wherever $l_i$ stands by its own, I wrote $l_i\vee l_i$... Nothing says I'm not allowed to use it. $\endgroup$ – so.very.tired Apr 15 '14 at 11:52
  • $\begingroup$ @so.very.tired I would disagree. The phrase exactly $k$ literals means just this. For example, given a $k$-CNF, a random assignment satisfies a $(1-2^{-k})$-fraction of the clauses. This is only true because the $k$ literals in each clause are distinct. $\endgroup$ – Yuval Filmus Apr 15 '14 at 17:51

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.