O problema de correspondência pós é mais de duas linhas mais duras que a variante padrão de duas filas?

Question

O problema de correspondência de postagem padrão diz respeito a azulejos com duas linhas de símbolos, e se um arranjo de azulejos pode ser feito para que a sequência dos símbolos superiores das telhas seja igual à parte inferior.

Deixe $ \ text {n-pcp}, \ text {n}> 0 $ uma generalização do problema de correspondência pós onde as telhas contêm $ \ text {n} $ linhas, e as sequências dos símbolos devem ser iguais para todas essas linhas.

Obviamente $ \ text {1-pcp} $ é decidível (na verdade, é trivial porque a resposta para o problema é sempre verdadeira). $ \ text {2-pcp} $ é o PCP padrão.

Mas e se $ \ text {n}> 2 $ ?É mais difícil ou pode ser reduzido ao PCP padrão (como> 3-sentado sendo reduzido para 3-SAT)?

Answer 1

$ \ text {n-pcp} $ pode ser reduzido para $ \ text {2-pcp} $ como segue.

Deixe $ m $ ser uma máquina de Turing não interminista que aceita uma $ \ text {n-pcp} $ Instância como entrada, adivinha uma solução para essa instância e, em seguida, verifica se está correta.Claramente, $ m $ aceita se e somente se houver uma solução para a instância de entrada.

Agora, deixe $ P $ ser uma instância de $ \ texto {n-pcp} $ .A redução codifica $ m (p) $ como uma $ \ text {2-pcp} $ instance ema moda padrão.