# 3-SAT to Max-2-SAT Reduction

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.

• 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? $\;\;\;\;\;\;$
– user12859
Apr 12, 2014 at 19:39
• You know what? they didn't say anything about not using $x\vee x$... so I think I'll go with it. Apr 12, 2014 at 21:29
• I don't think $x\lor x$ is legit. Otherwise it would be pointless to require that there be exactly two literals. Apr 13, 2014 at 23:02

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$.
• 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. Apr 15, 2014 at 11:52
• @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. Apr 15, 2014 at 17:51