Problema de correspondencia postal

El problema de correspondencia de Post es un problema de decisión indecidible que fue introducido por Emil Post en 1946. ^[1] Debido a que es más simple que el problema de detención y el problema de Entscheidung, a menudo se utiliza en pruebas de indecidibilidad.

Definición del problema

Sea un alfabeto con al menos dos símbolos. La entrada del problema consta de dos listas finitas y de palabras de más de . Una solución a este problema es una secuencia de índices con y para todo , tal que ${\displaystyle A}$ ${\displaystyle \alpha _{1},\ldots ,\alpha _{N}}$ ${\displaystyle \beta _{1},\ldots ,\beta _{N}}$ ${\displaystyle A}$ ${\displaystyle (i_{k})_{1\leq k\leq K}}$ ${\displaystyle K\geq 1}$ ${\displaystyle 1\leq i_{k}\leq N}$ ${\displaystyle k}$

${\displaystyle \alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.}$

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

Definición alternativa

${\displaystyle g:(i_{1},\ldots ,i_{K})\mapsto \alpha _{i_{1}}\ldots \alpha _{i_{K}}}$

${\displaystyle h:(i_{1},\ldots ,i_{K})\mapsto \beta _{i_{1}}\ldots \beta _{i_{K}}.}$

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

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

Otra definición describe este problema fácilmente como un tipo de rompecabezas. Comenzamos con una colección de dominós, cada uno con dos cuerdas, una en cada lado. Un dominó individual se ve así:

${\displaystyle {\begin{bmatrix}a\\ab\end{bmatrix}}}$

y una colección de dominós parece

${\displaystyle {{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}}$.

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

${\displaystyle {{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}}$.

En el caso de algunas colecciones de dominós, puede que no sea posible encontrar una pareja. Por ejemplo, la colección

${\displaystyle {{\begin{bmatrix}abc\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}acc\\ba\end{bmatrix}}}}$.

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

Ejemplos de casos del problema

Ejemplo 1

Considere las dos listas siguientes:

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

${\displaystyle \alpha _{3}\alpha _{2}\alpha _{3}\alpha _{1}=bba\cdot ab\cdot bba\cdot a=bbaabbbaa=bb\cdot aa\cdot bb\cdot baa=\beta _{3}\beta _{2}\beta _{3}\beta _{1}.}$

Además, como (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 únicamente en y de esos conjuntos, entonces no habría habido solución (la última letra de cualquier cadena α no es la misma que la letra anterior, mientras que β solo construye pares de la misma letra). ${\displaystyle \alpha _{2},\alpha _{3}}$ ${\displaystyle \beta _{2},\beta _{3}}$

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

Hay un suministro ilimitado de cada tipo de bloque. Por lo tanto, el ejemplo anterior se considera como

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

Ejemplo 2

Nuevamente usando bloques para representar una instancia del problema, el siguiente es un ejemplo que tiene infinitas soluciones además del tipo que se obtiene 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 sería 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 de Michael Sipser Introducción a la teoría de la computación . ^[2]

En más detalle, la idea es que la cadena que se encuentra en la parte superior e inferior sea un historial de cómputo de la máquina de Turing. Esto significa que incluirá una cadena que describe el estado inicial, seguida de una cadena que describe el siguiente estado, y así sucesivamente hasta que finalice con una cadena que describe un estado de aceptación. Las cadenas de estado están separadas por un 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 de estados finitos que opera el cabezal de cinta.
• La posición actual del cabezal de la cinta en la cinta.

Aunque la cinta tiene infinitas celdas, solo algunos prefijos finitos de ellas no estarán en blanco. Los escribimos como parte de nuestro estado. Para describir el estado del control finito, creamos nuevos símbolos, etiquetados de q ₁ a q _k , para cada uno de los k estados 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, indicando así 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í:

101101110 q7 ₀₀₁₁₀ .

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

q ₀ 101#1 q ₄ 01#11 q ₂ 1#1 q ₈ 10.

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

El superior comienza "retrasándose" respecto del inferior en un estado y mantiene este retraso hasta la etapa final. A continuación, para cada símbolo a en el alfabeto de cinta, así como #, tenemos un bloque "copia", que lo copia sin modificaciones de un estado al siguiente:

También tenemos un bloque para cada transición de posición que puede realizar la máquina, mostrando 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 la parte superior alcanza un estado de aceptación, la parte inferior necesita una oportunidad de alcanzarla finalmente para completar la coincidencia. Para permitir esto, ampliamos el cálculo de modo que una vez que se alcanza un estado de aceptación, cada paso de máquina posterior hará que un símbolo cerca del cabezal de la cinta desaparezca, 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, asegurarnos de que nuestra ficha inicial va primero en el juego, etc., pero esto muestra la idea general de cómo un rompecabezas de fichas estático puede simular un cálculo de máquina de Turing.

El ejemplo anterior

q ₀ 101#1 q ₄ 01#11 q ₂ 1#1 q ₈ 10.

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

Variantes

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

• El problema puede formularse en términos de morfismos monoides f , g desde el monoide libre B ^∗ hasta el monoide libre A ^∗ donde B es de tamaño n . El problema es determinar si existe una palabra w en B ⁺ tal que f ( w ) = g ( w ). ^[3]
• Se requiere la condición de que el alfabeto tenga al menos dos símbolos, ya que el problema es decidible si solo tiene un símbolo. ${\displaystyle A}$ ${\displaystyle A}$
• Una variante sencilla es fijar n , el número de fichas. Este problema es decidible si n ≤ 2, ^[4] pero sigue siendo indecidible para n ≥ 5. Se desconoce si el problema es decidible para 3 ≤ n ≤ 4. ^[5]
• El problema de correspondencia circular de Post plantea la pregunta de si se pueden encontrar índices tales que y sean palabras conjugadas , es decir, que sean iguales módulo rotación. Esta variante es indecidible. ^[6] ${\displaystyle i_{1},i_{2},\ldots }$ ${\displaystyle \alpha _{i_{1}}\cdots \alpha _{i_{k}}}$ ${\displaystyle \beta _{i_{1}}\cdots \beta _{i_{k}}}$
• Una de las variantes más importantes del PCP es el problema de correspondencia de Post acotado , que pregunta si podemos encontrar una coincidencia utilizando no más de k mosaicos, incluidos los mosaicos repetidos. Una búsqueda de fuerza bruta resuelve el problema en un tiempo O(2 ^k ), pero esto puede ser difícil de mejorar, ya que el problema es NP-completo . ^[7] A diferencia de algunos problemas NP-completos como el problema de satisfacibilidad booleana , también se demostró que una pequeña variación del problema acotado es completa para 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). ^[8]
• Otra variante del PCP se denomina problema de correspondencia posterior marcada , en el que cada uno debe comenzar con un símbolo diferente, y cada uno también debe comenzar con un símbolo diferente. Halava, Hirvensalo y de Wolf demostraron que esta variación es decidible en tiempo exponencial . Además, demostraron que si este requisito se relaja ligeramente de modo que solo uno de los dos primeros caracteres debe diferir (el llamado problema de correspondencia posterior de 2 marcas), el problema se vuelve indecidible nuevamente. ^[9] ${\displaystyle \alpha _{i}}$ ${\displaystyle \beta _{i}}$
• El problema de la incrustación posterior es otra variante en la que se buscan índices tales que sea una subpalabra (dispersa) de . Esta variante es fácilmente decidible ya que, cuando existen algunas soluciones, en particular existe una solución de longitud uno. Más interesante es el problema de la incrustación posterior regular , otra variante en la que se buscan soluciones que pertenecen a un lenguaje regular dado (presentadas, por ejemplo, bajo la forma de una expresión regular en el conjunto ). El problema de la incrustación posterior regular sigue siendo decidible pero, debido a la restricción regular añadida, tiene una complejidad muy alta que domina toda función recursiva múltiple. ^[10] ${\displaystyle i_{1},i_{2},\ldots }$ ${\displaystyle \alpha _{i_{1}}\cdots \alpha _{i_{k}}}$ ${\displaystyle \beta _{i_{1}}\cdots \beta _{i_{k}}}$ ${\displaystyle \{1,\ldots ,N\}}$
• El problema de correspondencia de identidades (ICP) plantea la pregunta de si un conjunto finito de pares de palabras (sobre un alfabeto de grupo) puede generar un par de identidades mediante una secuencia de concatenaciones. El problema es indecidible y equivalente al siguiente problema de grupo: ¿el semigrupo generado por un conjunto finito de pares de palabras (sobre un alfabeto de grupo) es un grupo? ^[11]

Referencias

1. EL Post (1946). "Una variante de un problema recursivamente irresoluble" (PDF) . Bull. Amer. Math. Soc. 52 (4): 264–269. doi :10.1090/s0002-9904-1946-08555-9. S2CID  122948861.
2. Michael Sipser (2005). "Un problema simple e indecidible". Introducción a la teoría de la computación (2.ª ed.). Thomson Course Technology. págs. 199-205. ISBN 0-534-95097-3.
3. Salomaa, Arto (1981). Joyas de la teoría del lenguaje formal . Pitman Publishing. pp. 74–75. ISBN 0-273-08522-0.Zbl 0487.68064  .
4. Ehrenfeucht, A. ; Karhumäki, J. ; Rozenberg, G. (noviembre de 1982). "El problema de correspondencia posterior (generalizado) con listas que constan de dos palabras es decidible". Ciencias de la Computación Teórica . 21 (2): 119–144. doi :10.1016/0304-3975(89)90080-7.
5. T. Neary (2015). "Indecidibilidad en sistemas de etiquetas binarias y el problema de correspondencia posterior para cinco pares de palabras". En Ernst W. Mayr y Nicolas Ollinger (ed.). 32.º Simposio Internacional sobre Aspectos Teóricos de la Informática (STACS 2015) . STACS 2015. Vol. 30. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. págs. 649–661. doi : 10.4230/LIPIcs.STACS.2015.649 .
6. K. Ruohonen (1983). "Sobre algunas variantes del problema de correspondencia de Post". Acta Informatica . 19 (4). Springer: 357–367. doi :10.1007/BF00290732. S2CID  20637902.
7. Michael R. Garey ; David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman. p. 228. ISBN 0-7167-1045-5.
8. Y. Gurevich (1991). "Completitud media de los casos" (PDF) . J. Comput. Syst. Sci. 42 (3). Elsevier Science: 346–398. doi :10.1016/0022-0000(91)90007-R. hdl :2027.42/29307.
9. V. Halava; M. Hirvensalo; R. de Wolf (2001). "El PCP marcado es decidible". Theor. Comput. Sci . 255 (1–2). Elsevier Science: 193–204. doi :10.1016/S0304-3975(99)00163-2.
10. P. Chambart; Ph. Schnoebelen (2007). El problema de la incrustación posterior no es recursivo primitivo, con aplicaciones a los sistemas de canales (PDF) . Lecture Notes in Computer Science. Vol. 4855. Springer. págs. 265–276. doi :10.1007/978-3-540-77050-3_22. ISBN . 978-3-540-77049-7.
11. Paul C. Bell; Igor Potapov (2010). "Sobre la indecidibilidad del problema de correspondencia de identidad y sus aplicaciones para semigrupos de palabras y matrices". Revista internacional de fundamentos de la ciencia de la computación . 21 (6). World Scientific: 963–978. arXiv : 0902.1975 . doi :10.1142/S0129054110007660.

Enlaces externos

• Eitan M. Gurari. Introducción a la teoría de la computación , Capítulo 4, Problema de correspondencia de Post. Una prueba de la indecidibilidad de PCP basada en gramáticas de tipo 0 de Chomsky .
• Dong, Jing. "Análisis y solución de una instancia de PCP". Conferencia nacional de 2012 sobre tecnología de la información y ciencias de la computación. El artículo describe una regla heurística para resolver algunas instancias de PCP específicas.
• Solucionador de PCP en línea basado en PHP
• PCP EN CASA
• PCP - un problema agradable
• Solucionador PCP en Java
• Problema de correspondencia postal