[Solved]: A polynomial reduction from any NP-complete problem to bounded PCP

As is often the case with NP-reductions, it makes sense to look for similar problems. In particular, it is hard to encode global conditions such has “have seen some nodes” into PCP (with polynomially many tiles) which contraindicates graph problems, packing problems would require us to encode unary numbers in PCP (creating exponentially large instance), and so on. Therefore, a string problem with only local restrictions can be expected to work best. Consider the decision version of the shortest common supersequence problem:

Given two strings $a,b in Sigma^+$ with $|a|=n$ and $|b|=m$ and $k in mathbb{N}$, decide whether there is a string $c in Sigma^+$ with $|c| leq k$ such that $a$ and $b$ are subsequences of $c$.

The idea is to let PCP build supersequences of $a$ and $b$ from left to right, encoding in the tiles’ overlaps at which position we are in $a$ and $b$, respectively. It will use one tile per symbol in $c$, so $k$ corresponds to the BPCP’s bound: if we can solve this PCP with $leq k$ tiles, you can read off the common supersequence of equal length, and vice versa. The construction of the tiles is a bit tedious, but quite clear. Note that we will not create tiles that do not forward $a$ or $b$; such can never be part of a shortest common supersequence, so they are superfluous. They can easily be added without breaking the properties of the reduction. The numbers in the overlaps are encoded in binary, but using symbols outside of $Sigma$ and padding them to a common length $log max(m,n)$. Thus we ensure that the tiles are used as the graphics suggest (tetris), that is characters and index-encoding overlaps do not mix (PCP does not prevent this per se). We need:

• Starting tiles: $c$ can start with $a_1$, $b_1$ or both if they are equal.
• Intermediate tiles: $c$ can proceed with the next symbol in $a$, in $b$ or both if they are equal.
• Terminating tiles: $c$ ends with the last symbol of $a$ (if the last one of $b$ has been seen already), similar for $b$, or with the last symbol of both.

These are the tile schematics. Note that the intermediate tiles have to be instantiated for all pairs $(i,j) in [n]times [m]$. As mentioned above, create the tiles without $*$ only if the respective characters in $a$ and $b$ match.
[source] The $*$ are symbolic for “don’t care”; in the actual tiles, the other symbol will have to be copied there. Note that the number of tiles is in $Theta(mn)$ and each tile has length $4log max(m,n) + 1$, so the constructed BPCP instance (over alphabet $Sigma cup {0,1}$ plus separation symbols) has polynomial size. Furthermore, the construction of every tile is clearly possible in polynomial time. Therefore, the proposed reduction is indeed a valid polynomial transformation which reduces the NP-complete shortest common supersequence problem to BPCP.