Longest Common Sequence reduction proof question
We can prove that LCS (with an unbounded number of sequences!) is NP-hard by reduction from 3SAT. Let us be given a CNF $\varphi$ with $m$ clauses $C_j$ of the form
$$
(x_{i_{j,1}} = b_{j,1}) \lor (x_{i_{j,2}} = b_{j,2}) \lor (x_{i_{j,3}} = b_{j,3}).
$$
Here $b(j,c)$ is either T or F, and we assume that $i_{j,1},i_{j,2},i_{j,3}$ are all distinct.

We will consider the following strings:


$S_1 = x_{i_{1,1},1}^{b_{1,1}} x_{i_{1,2},1}^{b_{1,2}} x_{i_{1,3},1}^{b_{1,3}} \ldots x_{i_{m,1},m}^{b_{m,1}} x_{i_{m,2},m}^{b_{m,2}} x_{i_{m,3},m}^{b_{m,3}}$.
$S_2 = x_{i_{1,2},1}^{b_{1,2}} x_{i_{1,3},1}^{b_{1,3}} x_{i_{1,1},1}^{b_{1,1}} \ldots x_{i_{m,2},m}^{b_{m,2}} x_{i_{m,3},m}^{b_{m,3}} x_{i_{m,1},m}^{b_{m,1}}$.
$S_3 = x_{i_{1,3},1}^{b_{1,3}} x_{i_{1,1},1}^{b_{1,1}} x_{i_{1,2},1}^{b_{1,2}} \ldots x_{i_{m,3},m}^{b_{m,3}} x_{i_{m,1},m}^{b_{m,1}} x_{i_{m,2},m}^{b_{m,2}}$.


For each variable $x_i$, let $T_i$ be the string obtained from $S_1$ by removing all occurrences of $x_{i,j}^F$ (for all $j$), and let $F_i$ be the string obtained from $S_1$ by removing all occurrences of $x_{i,j}^T$. 


For each variable $x_i$, $TF_i = T_i F_i$ and $FT_i = F_i T_i$.


Let $R$ be a common subsequence of all these strings.


For every $j$, the string $R$ contains at most one of $x_{i_{j,1},j}^{b_{j,1}},x_{i_{j,2},j}^{b_{j,2}},x_{i_{j,3},j}^{b_{j,3}}$. Indeed, suppose that it contained both $x_{i_{j,k_1},j}^{b_{j,k_1}}$ and $x_{i_{j,k_2},j}^{b_{j,k_2}}$, in this order. Since $R$ is a subsequence of $S_1$, we must have $k_1 &lt; k_2$. However, if $k_1 = 1$ then $R$ cannot be a subsequence of $S_2$, and if $k_1 = 2$ then $R$ cannot be a subsequence of $S_3$.


Thus $|R| \leq m$, and if $|R| = m$ then we can associate with $R$ a choice of equation in each clause.

For every $i$, if $R$ contains both $x_{i,j_1}^{b_1}$ and $x_{i,j_2}^{b_2}$ then $b_1 = b_2$. Indeed, in any subsequence of $TF_i$ all symbols $x_{i,j_1}^T$ precede all symbols $x_{i,j_2}^F$, and in any subsequence of $FT_i$ all symbols $x_{i,j_1}^F$ precede all symbols $x_{i,j_2}^T$.


Thus the chosen equations are all compatible.



This shows that if $|R| = m$ then $\varphi$ is satisfiable. The converse is also easy to establish: given a satisfying assignment, we can choose a satisfied equation in each clause, and then concatenate the corresponding symbols.

Let us give an example. Consider the formula
$$
\varphi = [(x_1 = T) \lor (x_2 = T) \lor (x_3 = T)] \land [(x_2 = F) \lor (x_4=F) \lor (x_1 = F)].
$$
The strings are


$S_1 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$S_2 = x_{2,1}^T x_{3,1}^T x_{1,1}^T x_{4,2}^F x_{1,2}^F x_{2,2}^F$.
$S_3 = x_{3,1}^T x_{1,1}^T x_{2,1}^T x_{1,2}^F x_{2,2}^F x_{4,2}^F$.
$TF_1 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_1 = x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F$.
$TF_2 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_2 = x_{1,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{4,2}^F x_{1,2}^F$.
$TF_3 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_3 = x_{1,1}^T x_{2,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$TF_4 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F$.
$FT_4 = x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{4,2}^F x_{1,2}^F x_{1,1}^T x_{2,1}^T x_{3,1}^T x_{2,2}^F x_{1,2}^F$.


One string $R$ of length $m=2$ which is common to all of these is $x_{1,1}^T x_{2,2}^F$. This corresponds to the (partial) truth assignment $x_1=T,x_2=F$, which satisfies $\varphi$.