Problema de correspondencia postal

El problema de correspondencia posterior es un problema de decisión indecidible que fue presentado por Emil Post en 1946. Debido a que es más simple que el problema de detención y el Entscheidungsproblem, se usa a menudo en las pruebas de indecidibilidad.

Definición del problema

Vamos ${displaystyle A}$ ser un alfabeto con al menos dos símbolos. La entrada del problema consiste en dos listas finitas ${displaystyle alpha _{1},ldotsalpha ¿Qué?$ y ${displaystyle beta _{1},ldotsbeta ¿Qué?$ palabras sobre ${displaystyle A}$. Una solución a este problema es una secuencia de índices ${displaystyle (i_{k})_{1leq kleq K}$ con ${displaystyle Kgeq 1}$ y ${displaystyle 1leq I_{k}leq N.$ para todos ${displaystyle k}$, tal que

${displaystyle alpha # {i_{1}ldots alpha ¿Qué? # {i_{1}ldots beta - ¿Qué?$

El problema de decisión entonces es decidir si tal solución existe o no.

Definición alternativa

${displaystyle g:(i_{1},ldotsi_{K})mapsto alpha # {i_{1}ldots alpha ¿Qué?$

${displaystyle h:(i_{1},ldotsi_{K})mapsto beta # {i_{1}ldots beta - ¿Qué?$

Esto da lugar a una definición alternativa equivalente a menudo encontrada en la literatura, según la cual cualquier dos homomorfismos ${displaystyle g,h}$ con un dominio común y un codominio común forman una instancia del problema de correspondencia Post, que ahora pregunta si existe una palabra no vacía ${displaystyle w}$ en el dominio tal que

${displaystyle g(w)=h(w)}$.

Otra definición describe este problema fácilmente como un tipo de rompecabezas. Comenzamos con una colección de fichas de dominó, cada una de las cuales contiene dos cuerdas, una en cada lado. Un dominó individual parece

${displaystyle [a/ab]}$

y parece una colección de fichas de dominó

${displaystyle {[bc/ca],[a/ab],[ca/a],[abc/c]}}$.

La tarea es hacer una lista de estas fichas de dominó (se permite la repetición) para que la cadena que obtengamos al leer los símbolos en la parte superior sea la misma que la cadena de símbolos en la parte inferior. Esta lista se llama coincidencia. El problema de la correspondencia posterior es determinar si una colección de fichas de dominó tiene una coincidencia. Por ejemplo, la siguiente lista coincide con este rompecabezas.

${displaystyle {[a/ab],[bc/ca],[a/ab],[abc/c]}}$.

Para algunas colecciones de fichas de dominó, puede que no sea posible encontrar una coincidencia. Por ejemplo, la colección

${displaystyle {[abc/ab],[ca/a],[acc/ba]}$.

no puede contener una coincidencia porque cada cadena superior es más larga que la cadena inferior correspondiente.

Instancias de ejemplo del problema

Ejemplo 1

Considere las siguientes dos listas:

Una solución a este problema sería la secuencia (3, 2, 3, 1), porque

${displaystyle alpha _{3}alpha ### {2}alpha ################################################################################################################################################################################################################################################################ ##{1}=bbacdot abcdot bbacdot a=bbaabbbaa=bbcdot aacdot bbcdot baa=beta ¿Qué? ¿Qué? _{1}$

Además, dado que (3, 2, 3, 1) es una solución, también lo son todas sus "repeticiones", como (3, 2, 3, 1, 3, 2, 3, 1), etc.; es decir, cuando existe una solución, hay infinitas soluciones de este tipo repetitivo.

Sin embargo, si las dos listas hubieran consistido sólo en ${displaystyle alpha _{2},alpha ¿Qué?$ y ${displaystyle beta _{2},beta ¿Qué?$ de esos conjuntos, entonces no habría habido solución (la última letra de tal cadena α no es la misma que la letra antes de ella, mientras que β sólo construye pares de la misma letra).

Una forma conveniente de ver una instancia de un problema de correspondencia de Post es como una colección de bloques de la forma

existiendo una oferta ilimitada de cada tipo de bloque. Así, el ejemplo anterior se considera como

donde el solucionador tiene un suministro ilimitado de cada uno de estos tres tipos de bloques. Una solución corresponde a alguna forma de colocar bloques uno al lado del otro de modo que la cuerda en las celdas superiores corresponda a la cuerda en las celdas inferiores. Entonces la solución al ejemplo anterior corresponde a:

Ejemplo 2

Usando nuevamente bloques para representar una instancia del problema, el siguiente es un ejemplo que tiene infinitas soluciones además del tipo obtenido simplemente "repitiendo" una solución.

En este caso, cada secuencia de la forma (1, 2, 2,..., 2, 3) es una solución (además de todas sus repeticiones):

Esquema de prueba de indecidibilidad

La prueba más común de la indecidibilidad de PCP describe una instancia de PCP que puede simular el cálculo de una máquina de Turing arbitraria en una entrada particular. Se producirá una coincidencia si y solo si la entrada es aceptada por la máquina de Turing. Debido a que decidir si una máquina de Turing aceptará una entrada es un problema indecidible básico, PCP tampoco puede ser decidible. La siguiente discusión se basa en el libro de texto Introducción a la teoría de la computación de Michael Sipser.

En más detalle, la idea es que la cadena a lo largo de la parte superior e inferior sea un historial de cálculo del cálculo de la máquina de Turing. Esto significa que mostrará una cadena que describe el estado inicial, seguida de una cadena que describe el siguiente estado, y así sucesivamente hasta que termina con una cadena que describe un estado de aceptación. Las cadenas de estado están separadas por algún símbolo separador (generalmente escrito #). Según la definición de una máquina de Turing, el estado completo de la máquina consta de tres partes:

• El contenido actual de la cinta.
• El estado actual de la máquina estatal finita que opera la cabeza de cinta.
• La posición actual de la cabeza de cinta en la cinta.

Aunque la cinta tiene un número infinito de celdas, solo algunos prefijos finitos de estos no estarán en blanco. Los escribimos como parte de nuestro estado. Para describir el estado del control finito, creamos nuevos símbolos, etiquetados q₁ a q_k, para cada uno de los estados k de la máquina de estados finitos. Insertamos el símbolo correcto en la cadena que describe el contenido de la cinta en la posición del cabezal de la cinta, lo que indica tanto la posición del cabezal de la cinta como el estado actual del control finito. Para el alfabeto {0,1}, un estado típico podría verse así:

101101110q₇00110.

Un historial de cálculo simple se vería así:

q₀101#1q₄01#11q< sub>21#1q₈10.

Empezamos con este bloque, donde x es la cadena de entrada y q₀ es el estado inicial:

La parte superior comienza "rezagada" la parte inferior por un estado, y mantiene este retraso hasta la etapa final. A continuación, para cada símbolo a en el alfabeto de la cinta, así como #, tenemos una "copia" bloque, que lo copia sin modificar de un estado al siguiente:

También tenemos un bloque para cada transición de posición que puede hacer la máquina, que muestra cómo se mueve el cabezal de la cinta, cómo cambia el estado finito y qué sucede con los símbolos circundantes. Por ejemplo, aquí el cabezal de la cinta está sobre un 0 en el estado 4 y luego escribe un 1 y se mueve hacia la derecha, cambiando al estado 7:

Finalmente, cuando el superior alcanza un estado de aceptación, el inferior necesita la oportunidad de ponerse al día para completar el partido. Para permitir esto, ampliamos el cálculo de modo que una vez que se alcanza un estado de aceptación, cada paso subsiguiente de la máquina hará que desaparezca un símbolo cerca del cabezal de la cinta, uno a la vez, hasta que no quede ninguno. Si q_f es un estado de aceptación, podemos representarlo con los siguientes bloques de transición, donde a es un símbolo del alfabeto de cinta:

Hay una serie de detalles que resolver, como lidiar con los límites entre estados, asegurarse de que nuestra ficha inicial sea la primera en la partida, etc., pero esto muestra la idea general de cómo un rompecabezas de fichas estáticas puede simular un cálculo de la máquina de Turing.

El ejemplo anterior

q₀101#1q₄01#11q< sub>21#1q₈10.

se representa como la siguiente solución al problema de la correspondencia postal:

Variantes

Se han considerado muchas variantes de PCP. Una de las razones es que, cuando se intenta probar la indecidibilidad de algún problema nuevo mediante la reducción del PCP, a menudo sucede que la primera reducción que se encuentra no es del propio PCP sino de una versión aparentemente más débil.

• El problema puede ser expresado en términos de morfismos monoideos f, g del monoide libre B^Alternativa al monoide libre A^Alternativa Donde B es de tamaño n. El problema es determinar si hay una palabra w dentro B⁺ tales que f()w) g()w).
• La condición de que el alfabeto ${displaystyle A}$ tiene al menos dos símbolos es necesario ya que el problema es decidable si ${displaystyle A}$ sólo tiene un símbolo.
• Una variante simple es arreglar n, el número de fichas. Este problema es decidable si n ≤ 2, pero sigue siendo indecible n ≥ 5. Se desconoce si el problema es decidable para 3 ≤ n ≤ 4.
• El circular circular Problema de correspondencia postal pregunta si índices ${displaystyle i_{1},i_{2},ldots }$ se puede encontrar tal que ${displaystyle alpha ¿Por qué? ¿Qué?$ y ${displaystyle beta ¿Por qué? ¿Qué?$ son palabras conjugadas, es decir, son rotación de modulo igual. Esta variante es indecible.
• Una de las variantes más importantes del PCP es la atado Problema de correspondencia postal, que pregunta si podemos encontrar una coincidencia usando no más que k azulejos, incluyendo baldosas repetidas. Una búsqueda de fuerza bruta resuelve el problema en el tiempo O(2^k), pero esto puede ser difícil de mejorar, ya que el problema es NP-completo. A diferencia de algunos problemas completos de NP como el problema de la satisfiabilidad booleana, también se mostró una pequeña variación del problema ligado para la RNP, lo que significa que sigue siendo difícil incluso si las entradas se eligen al azar (es difícil en promedio sobre entradas distribuidas uniformemente).
• Otra variante del PCP se llama la marcado Problema de correspondencia post, en que cada ${displaystyle alpha _{i}$ debe comenzar con un símbolo diferente, y cada uno ${displaystyle beta _{i}$ también debe comenzar con un símbolo diferente. Halava, Hirvensalo y de Wolf mostraron que esta variación es decida en tiempo exponencial. Además, demostraron que si este requisito se afloja ligeramente para que sólo uno de los dos primeros caracteres tenga que diferir (el llamado Problema de Correspondencia Postal 2-marked), el problema se vuelve indecible de nuevo.
• El Problema de inserción de puestos es otra variante donde uno busca índices ${displaystyle i_{1},i_{2},ldots }$ tales que ${displaystyle alpha ¿Por qué? ¿Qué?$ es una subpalabra (scattered) ${displaystyle beta ¿Por qué? ¿Qué?$. Esta variante es fácilmente decidable ya que, cuando existen algunas soluciones, en particular existe una solución longitud-uno. Más interesante es el Recursos ordinarios Problema de inserción de puestos, otra variante en la que se busca soluciones que pertenecen a un idioma regular determinado (presentado, por ejemplo, bajo la forma de una expresión regular en el conjunto ${displaystyle {1,ldotsN}$). El Problema de Embedding Post Regular sigue siendo decidable pero, debido a la limitación regular agregada, tiene una complejidad muy alta que domina cada función recursiva multiplicada.
• El Problema de correspondencia de identidad (ICP) pregunta si un conjunto finito de pares de palabras (sobre un alfabeto de grupo) puede generar un par de identidad por una secuencia de concatenaciones. El problema es indecible y equivalente al siguiente problema de grupo: es el semigrupo generado por un conjunto finito de pares de palabras (sobre un alfabeto de grupo) un grupo.