# 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 '14 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. – so.very.tired Apr 12 '14 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. – Yuval Filmus Apr 13 '14 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. – so.very.tired Apr 15 '14 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. – Yuval Filmus Apr 15 '14 at 17:51