How exactly does a Max 2 Sat reduce to a 3 Sat?

Question

Note: I've also asked this question on StackOverflow here

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.

Answer 1

First, the article is reducing 3SAT to Max2SAT (not Max2SAT to 3SAT).
In 3SAT, each clause has 3 variables and has the form $c_i=(l_1 \cup l_2 \cup l_3)$.

For each clause $c_i$, create the following 10 clauses:

$(l_1), (l_2), (l_3), (d_i), (\lnot l_1 \cup \lnot l_2), (\lnot l_2 \cup \lnot l_3), (\lnot l_1 \cup \lnot l_3), (l_1 \cup \lnot d_i), (l_2 \cup \lnot d_i), (l_3 \cup \lnot d_i)$

There are 8 possible truth assigments to $(l_1, l_2, l_3)$:
(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)

The assignment (0, 0, 0) will not satisfy $c_i$.
This assigment will not satisfy more than 6 clauses regardless of whether we assign $d_i=0$ or $d_i=1$
(try making the assignments to the variables to see for yourself).

The assignments (0, 0, 1), (0, 1, 0) and (1, 0, 0) will satisfy $c_i$
With $d_i=0$ it will satisfy exactly 7 of the 10 clauses

The remaining 4 assignments will satisfy $c_i$ and each of the assignments will satisfy exactly 7 of the 10 clauses regardless of whether we assign $d_i=0$ or $d_i=1$ (again try making the assignments to see for yourself).

So, given a 3-SAT formula with m clauses the reduction to Max2SAT is:

1) for each clause in the 3SAT formula $c_1, c_2,..., c_m$ create the corresponding 10 clauses.
$\;\;\;$So, we have 10m clauses for Max2SAT.

2) Any assignment that satisfies the 3SAT formula must satisfy all m clauses.
$\;\;\;$ Satisfying 1 clause in 3SAT satisfies exactly 7 clauses in the corresponding 10 clauses of $\;\;\;$Max2SAT.
$\;\;\;$Hence, satisfying all m clauses in 3SAT means satisfying exactly 7m clauses in Max2SAT.
$\;\;\;$So, set k = 7m in the Max2SAT problem.

So, since we know 3SAT is NP-Complete, this means that unless P = NP, that Max2SAT must also be NP-Complete.

Hope this helps.