You're a bit confused about the terminology: in order to show that HAMPATH is NP-complete, you need to show that it's in NP (that's very easy) and that every problem in NP reduces to it. You do that by reducing some other NP-complete problem to HAMPATH.
As Theo noted, 3SAT is a special case of SAT, and so it's easier use 3SAT. The reduction that works for SAT will also work for 3SAT, but it may need to handle more cases. I'm not familiar with this particular reduction, but it might be that it's actually straightforward to generalize it to the "general case", but there's nothing to be gained by doing it.
Reductions showing a problem is NP-complete are usually like that - very intricate and slightly hard to follow. But usually there's the main idea - e.g., what corresponds to variables, what corresponds to clauses, why it should work - and the technical details. See first that you understand the main idea.
The technical details break into two parts. One part is the gadgets - you need to understand what the gadgets are supposed to do and how they accomplish it. The second part is proving that the construction works. In your case, it's probably easy to show that if the 3SAT instance is satisfiable, then the graph has a Hamiltonian path. It's probably more difficult to show that if the instance is unsatisfiable, the graph doesn't have any Hamiltonian paths. There's some intuition which leads us to believe that to be the case, but we still have to prove it, and the proof might be tricky.
Don't get discouraged if you don't "get it" right away. The best thing to understand these proofs is to do some of your own. Only then can you appreciate the thought processes behind such proofs. Better still, you might try working out a similar proof yourself, and see where you get stuck. There are some obstacles to overcome, and if you're aware of them then the construction will become much more interesting.
Looking at the reduction, I think Sisper explains it pretty well. In fact, for an expert it might be enough to mostly look at all the figures. The pattern of this reduction is very standard, so once you understand this one, you'll be in much better position to understand a whole lot of them!
The idea is to have variable-gadgets and clause-gadgets. The variable-gadgets can be traversed in two ways (according to the truth assignment). The clause-gadgets can be traversed-through from a satisfying literal.
So far for the idea. The construction itself is pretty simple, and it's easy to check that if a formula is satisfiable then there's a Hamiltonian path. It's also easy to see that if there's a similarly-looking Hamiltonian path then there's a satisfying assignment. The hard part is showing that all Hamiltonian paths "look as if they came out from a truth assignment", which must be satisfying.
I'm using a second answer to answer your newly added question. You made a little mistake, the cell formula should be the following:
$$\phi_{cell} = \underset{1\leqslant i, j\leqslant n^{k}}{\wedge }\left [ \left ( \underset {s\epsilon C}{\vee} x_{i,j,s} \right ) \wedge \left (\underset{\underset{s\neq t}{s,t\epsilon C}}{\wedge} \left ( \overline{x_{i,j,s}} \vee \overline{x_{i,j,t}} \right ) \right ) \right ]$$
As you said, the variable $x_{i,j,s}$ represents the symbol s in cell[i,j], so it should be true if and only iff cell[i,j] contains the symbol $s$. Let's analyse the cell formula properly. It exists out of 3 parts:
- $\Large\underset {s\epsilon C}{\vee} x_{i,j,s}$ tells that for each fixed $i$ and $j$ there should be atleast one symbol $s$ in cell[i,j].
- $\large\underset{\underset{s\neq t}{s,t\epsilon C}}{\wedge} \left ( \overline{x_{i,j,s}} \vee \overline{x_{i,j,t}} \right )$ says that, for each distinct pair of symbols $s$ and $t$: $\large x_{i,j,s}$ and $\large x_{i,j,t}$ cannot both be true at the same time. This represents that a cell cannot have more then one symbol.
Combining both points tells us that for each fixed $i$ and $j$ there has to be exactly one symbol $s$ ( NOT MORE AND NOT LESS) so that variable $x_{i,j,s} = 1$. More intuitively it tells us that each cell can only contain exactly one symbol.
Now the only thing left is to analyse is the $\large\underset{1\leqslant i, j\leqslant n^{k}}{\wedge }$ part encapsulating the parts we already analysed. Clearly this part just tells us that the formula has to hold for each cell in the tableau.
I hope this helped.
Best Answer
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.