Post Correspondence Problem
O Post Correspondence Problem (PCP), introduzido por Emil Post em 1946, é um problema de decisão indecidível. O problema PCP sobre um alfabeto ∑ é declarado da seguinte forma -
Dadas as duas listas a seguir, M e N de strings não vazias em ∑ -
M = (x 1 , x 2 , x 3 , ………, x n )
N = (y 1 , y 2 , y 3 , ………, y n )
Podemos dizer que existe uma solução de pós-correspondência, se para algum i 1 , i 2 , ………… i k , onde 1 ≤ i j ≤ n, a condição x i1 …… .x ik = y i1 ……. y ik satisfaz.
Exemplo 1
Descubra se as listas
M = (abb, aa, aaa) e N = (bba, aaa, aa)
tem uma solução de correspondência postal?
Solução
| x 1 | x 2 | x 3 | |
|---|---|---|---|
| M | Abb | aa | aaa |
| N | Bba | aaa | aa |
Aqui,
x2x1x3 = ‘aaabbaaa’
e y2y1y3 = ‘aaabbaaa’
Nós podemos ver isso
x2x1x3 = y2y1y3
Portanto, a solução é i = 2, j = 1, and k = 3.
Exemplo 2
Descubra se as listas M = (ab, bab, bbaaa) e N = (a, ba, bab) tem uma solução de correspondência postal?
Solução
| x 1 | x 2 | x 3 | |
|---|---|---|---|
| M | ab | babinha | bbaaa |
| N | uma | BA | babinha |
Neste caso, não há solução porque -
| x2x1x3 | ≠ | y2y1y3 | (Os comprimentos não são iguais)
Portanto, pode-se dizer que este problema de pós-correspondência é undecidable.