標準の2列のバリアントよりも2列を超える行を持つ投稿対応の問題は？

Question

標準投稿対応問題は、2行のシンボルを有するタイル、およびタイルの上部シンボルのシーケンスが下部に等しくなるようにタイル配置を行うことができるかどうか。

$ \ text {n-pcp}、\ text {n}> 0 $ タイルに $ \ text {n} $ 行、およびシンボルのシーケンスは、これらの行すべてに等しい必要があります。

明らかに $ \ text {1-pcp} $ は、（実際には問題に対する答えが常に真実であるため、それは簡単です）。 $ \ text {2-pcp} $ は標準のPCPです。

しかし $ \ text {n}> 2 $ の場合それは難しいか、それが標準のPCP（3-SATに縮小されている）に縮小することができますか？

Answer 1

$ \ text {n-pcp} $ は $ \ text {2-pcp} $ <に縮小できます。/スパン>以下のように。

$ m $ $ \ text {n-pcp} $ インスタンスとしてインスタンスとして、そのインスタンスの解決策を推測してから、正しいことを確認します。明らかに、 $ m $ 入力インスタンスの解決策がある場合に限り、

今、 $ p $ のインスタンスになる $ \ text {n-pcp} $ 。縮小エンコード $ m（p）$ として $ \ text {2-pcp} $ インスタンス標準的な方法。