Problema de correspondencia postal

No confundir con el problema del otro Post sobre la existencia de incomparables grados de Turing.

No confundir con el teorema de PCP .

El problema de la 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 la detención y el Entscheidungsproblem , a menudo se usa 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 over . Una solución a este problema es una secuencia de índices con y para todos , de modo 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 entonces es 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 posterior, que ahora pregunta si existe una palabra no vacía en el dominio tal ese${\displaystyle g,h}$${\displaystyle w}$

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

Otra definición describe este problema fácilmente como una especie de rompecabezas. Comenzamos con una colección de dominós, cada uno con dos cuerdas, una a cada lado. Un dominó individual parece

${\displaystyle [a/ab]}$

y una colección de dominó parece

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

La tarea es hacer una lista de estos dominós (se permite la repetición) de modo 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 posterior a la correspondencia consiste en 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 dominó, es posible 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.

Ejemplos de casos del problema

Ejemplo 1

Considere las siguientes dos listas:

α 1 α 2 α 3 a ab bba

β 1 β 2 β 3 balido Automóvil club británico cama y desayuno

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, 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 solo 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 del formulario

α yo β yo

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

a balido i = 1

ab Automóvil club británico i = 2

bba cama y desayuno i = 3

donde el solucionador tiene un suministro interminable 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:

bba cama y desayuno yo 1 = 3

ab Automóvil club británico yo 2 = 2

bba cama y desayuno yo 3 = 3

a balido yo 4 = 1

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.

cama y desayuno B 1

ab licenciado en Letras 2

C antes de Cristo 3

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

cama y desayuno B 1

ab licenciado en Letras 2

ab licenciado en Letras 2

ab licenciado en Letras 2

C antes de Cristo 3

Esbozo 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 máquina de Turing acepta la entrada. Debido a que decidir si una máquina de Turing aceptará una entrada es un problema básico indecidible , la PCP tampoco se puede decidir. La siguiente discusión se basa en el libro de texto Introducción a la teoría de la computación de Michael Sipser . ^[2]

Más detalladamente, 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 enumerará una cadena que describe el estado inicial, seguida de una cadena que describe el siguiente estado, y así sucesivamente hasta que termine con una cadena que describa un estado de aceptación. Las cadenas de estado están separadas por algún símbolo separador (normalmente 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 un número infinito de celdas, solo algunos prefijos finitos de estas 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, 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í:

101101110 q ₇ 00110.

Un historial de cálculo simple se vería 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 de inicio:

q 0 x #

La parte superior comienza "retrasando" la parte inferior en 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 un bloque de "copia", que lo copia sin modificar de un estado al siguiente:

a

a

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:

q 4 0

1 q 7

Finalmente, cuando la parte superior alcanza un estado de aceptación, la parte inferior necesita una oportunidad para finalmente ponerse al día para completar el partido. Para permitir esto, ampliamos el cálculo de modo que una vez que se alcance un estado de aceptación, cada paso subsiguiente de la máquina 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:

q f a q f

aq f q f

Hay una serie de detalles que resolver, como lidiar con los límites entre estados, asegurarnos de que nuestro mosaico inicial sea el primero en la coincidencia, y así sucesivamente, pero esto muestra la idea general de cómo un rompecabezas de mosaico estático puede simular un Turing. computación de la máquina.

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:

q 0 101 #

q 0 1 1 q 4

0 0

1 1

# #

1 1

q 4 0 1 q 2

1 1

# #

1 1

1 q 2 1 q 8 10

# #

1 q 8 q 8

1 1

0 0

# #

q 8 1 q 8

0 0

# #

q 8 0 q 8

# #

q 8

# #

...

Variantes

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

• El problema puede expresarse en términos de morfismos de monoide f , g desde el monoide libre B ^∗ al monoide libre A ^∗ donde B es de tamaño n . El problema es determinar si hay 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 simple es fijar n , el número de mosaicos. Este problema es decidible si n ≤ 2, ^[4] pero permanece indecidible para n ≥ 5. Se desconoce si el problema es decidible para 3 ≤ n ≤ 4. ^[5]
• El problema de correspondencia circular de Post pregunta si los índices se pueden encontrar de manera que y son palabras conjugadas , es decir, tienen la misma rotación de módulo. 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 de PCP es el problema de correspondencia de Post acotado , que pregunta si podemos encontrar una coincidencia utilizando no más de k mosaicos, incluidos mosaicos repetidos. 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 . ^[7] A diferencia de algunos problemas NP-completos como el problema de satisfacibilidad booleano , 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 para promedio sobre entradas distribuidas uniformemente). ^[8]
• Otra variante de PCP se denomina Problema de correspondencia posterior marcado , en el que cada uno debe comenzar con un símbolo diferente y 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 afloja ligeramente de modo que solo uno de los dos primeros caracteres deba diferir (el llamado Problema de correspondencia posterior a la marca 2), el problema se vuelve indecidible nuevamente. ^[9]${\displaystyle \alpha _{i}}$${\displaystyle \beta _{i}}$
• El problema posterior a la incrustación es otra variante en la que se buscan índices como 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 incrustación posterior regular , una variante adicional en la que se buscan soluciones que pertenecen a un lenguaje regular dado (enviadas, por ejemplo, bajo la forma de una expresión regular en el conjunto ). El problema de incrustación posterior regular todavía es decidible pero, debido a la restricción regular agregada, tiene una complejidad muy alta que domina todas las funciones recursivas múltiples. ^[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 Identidad (ICP) pregunta si un conjunto finito de pares de palabras (sobre un alfabeto grupal) puede generar un par de identidad mediante una secuencia de concatenaciones. El problema es indecidible y equivalente al siguiente Problema de grupo: es el semigrupo generado por un conjunto finito de pares de palabras (sobre un alfabeto grupal) un grupo. ^[11]

Referencias

1. EL Post (1946). "Una variante de un problema recursivamente irresoluble" (PDF) . Toro. Amer. Matemáticas. Soc . 52 (4): 264–269. doi : 10.1090 / s0002-9904-1946-08555-9 .
2. Michael Sipser (2005). "Un simple problema indecidible". Introducción a la Teoría de la Computación (2ª ed.). Tecnología del curso Thomson. págs. 199–205. ISBN 0-534-95097-3.
3. Salomaa, Arto (1981). Joyas de la teoría del lenguaje formal . Pitman Publishing. págs. 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 postal (generalizado) con listas que constan de dos palabras es decidible" . Informática 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. 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 . Saltador. 19 (4): 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 NP-Completeness . WH Freeman. pag. 228 . ISBN 0-7167-1045-5.
8. Y. Gurevich (1991). "Completitud de casos promedio" (PDF) . J. Comp. Sys. Sci . Ciencia de Elsevier. 42 (3): 346–398. doi : 10.1016 / 0022-0000 (91) 90007-R . hdl : 2027,42 / 29307 .
9. V. Halava; M. Hirvensalo; R. de Wolf (2001). "La PCP marcada es decidible". Theor. Computación. Sci . Ciencia de Elsevier. 255 (1–2): 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 sistemas de canal" (PDF) . Apuntes de conferencias en Ciencias de la Computación. 4855 . Springer: 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 . World Scientific. 21 (6): 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 la PCP basada en las gramáticas de tipo 0 de Chomsky .
• Dong, Jing. "El análisis y la solución de una instancia de PCP". 2012 Congreso Nacional de Tecnología de la Información e Informática. El documento describe una regla heurística para resolver algunos casos específicos de PCP.
• Solucionador de PCP basado en PHP en línea
• PCP EN CASA
• PCP: un buen problema
• Solucionador de PCP en Java