是后对应问题，与标准的双行变量难以超过两行？

Question

标准后对应问题涉及具有两行符号的瓷砖，以及是否可以进行瓦片布置，使得图块的顶部符号的序列等于底部。

let $ \ text {n-pcp}，\ text {n}> 0 $ 在图号包含 $ \ text {n} $ 行，并且符号的序列必须与所有这些行相等。

显然 $ \ text {1-pcp} $ 是可解除的（实际上它是琐碎的，因为问题的答案总是真的）。 $ \ text {2-pcp} $ 是标准pcp。

但如果 $ \ text {n}> 2 $ ？它越难以还是可以减少到标准PCP（如> 3-SAT被减少到3-SAT）？

Answer 1

$ \ text {n-pcp} $ 可以减少到 $ \ text {2-pcp} $ 如下。

let $ m $ 是一个非识别的图灵图，接受 $ \ text {n-pcp} $ 实例为输入，猜测该实例的解决方案，然后检查它是否正确。显然， $ m $ 只有在输入实例有解决方案时才接受。

现在，让 $ p $ 是 $ \ text {n-pcp} $ 的一个实例。缩减编码 $ m（p）$ 作为 $ \ text {2-pcp} $ 实例标准时尚。