Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant?

Question

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} > 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} > 2$? Is it harder or can it be reduced to the standard PCP (like >3-SAT being reduced to 3-SAT)?

Aaron Rotenberg · Answer

$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.

Is the Post Correspondence Problem with more than two rows harder than the standard two-row variant?

One Answer

Add your own answers!

Ask a Question