Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant? The standard Post Correspondence Problem concerns tiles with two rows of symbols, and whether a tile arrangement can be made so that the sequence of the top symbols of the tiles is equal to the bottom one.
Let $\text{n-PCP}, \text{n} &gt; 0$ a generalization of the Post Correspondence Problem where the tiles contain $\text{n}$ rows, and the sequences of the symbols have to be equal for all of these rows.
Obviously $\text{1-PCP}$ is decidable (in fact it's trivial because the answer to the problem is always true). $\text{2-PCP}$ is the standard PCP.
But what if $\text{n} &gt; 2$? Is it harder or can it be reduced to the standard PCP (like &gt;3-SAT being reduced to 3-SAT)?
$\text{n-PCP}$ can be reduced to $\text{2-PCP}$ as follows.
Let $M$ be a nondeterministic Turing machine that accepts an $\text{n-PCP}$ instance as input, guesses a solution for that instance, and then checks that it is correct. Clearly, $M$ accepts if and only if there is a solution to the input instance.
Now, let $p$ be an instance of $\text{n-PCP}$. The reduction encodes $M(p)$ as a $\text{2-PCP}$ instance in the standard fashion.