¿Es el problema posterior a la correspondencia con más de dos filas más duras que la variante estándar de dos filas?

Question

El problema de la correspondencia posterior estándar se refiere a los azulejos con dos filas de símbolos, y si se puede hacer una disposición de azulejos para que la secuencia de los símbolos superiores de los azulejos sea igual a la inferior.

Let $ \ Text {N-PCP}, \ Text {n}> 0 $ Una generalización del problema de la correspondencia posterior donde las fichas contienen $ \ texto {n} $ filas, y las secuencias de los símbolos deben ser iguales para todas estas filas.

obviamente $ \ texto {1-PCP} $ es decidible (de hecho, es trivial porque la respuesta al problema es siempre verdadera). $ \ Text {2-PCP} $ es el PCP estándar.

Pero, ¿qué pasa si $ \ texto {n}> 2 $ ?¿Es más difícil o puede reducirse al PCP estándar (como> 3-SAT se reduce a 3-SAT)?

Answer 1

$ \ texto {n-pcp} $ se puede reducir a $ \ texto {2-PCP} $ de la siguiente manera.

Let $ m $ Sé una máquina de Turing no determinista que acepte un $ \ texto {n-PCP} $ Instancia como entrada, adivina una solución para esa instancia, y luego verifica que es correcta.Claramente, $ m $ acepta si y solo si hay una solución a la instancia de entrada.

Ahora, permita que $ P $ sea una instancia de $ \ texto {n-PCP} $ .La reducción codifica $ m (p) $ como un $ \ texto {2-PCP} $ instancia enla moda estándar.