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.