Le problème post correspondant avec plus de deux rangées est-il plus difficile que la variante standard à deux rangées?

Question

Le problème de correspondance standard post concerne les carreaux avec deux rangées de symboles et si une disposition de tuile peut être apportée de manière à ce que la séquence des symboles supérieurs des carreaux soit égale à celle du bas.

let $ \ text {n-pcp}, \ text {n}> 0 $ une généralisation du problème de correspondance post où les tuiles contiennent $ \ texte {n} $ lignes et les séquences des symboles doivent être égales pour toutes ces lignes.

évidemment $ \ texte {1-pcp} $ est décidable (en fait, il est trivial parce que la réponse au problème est toujours vraie). $ \ texte {2-pcp} $ est le PCP standard.

Mais si $ \ texte {n}> 2 $ ?Est-ce plus difficile ou peut-il être réduit au PCP standard (comme> 3-SAT étant réduit à 3-sat)?

Answer 1

$ \ texte {n-pcp} $ peut être réduit à $ \ texte {2-pcp} $ comme suit.

let $ M $ soit une machine de turicing non déterministe qui accepte une $ \ text {n-pcp} $ instance comme entrée, devine une solution pour cette instance, puis vérifie qu'il est correct.Clairement, $ m $ accepte si et uniquement s'il existe une solution à l'instance d'entrée.

Maintenant, laissez $ p $ être une instance de $ \ texte {n-pcp} $ .La réduction codes $ m (p) $ comme une $ \ texte {2-pcp} $ la mode standard.