Problema da correspondência de Post

O problema da correspondência de Post é um problema de decisão indecidível que foi introduzido por Emil Post em 1946.. PCP é mais simples que o problema da parada e o Entscheidungsproblem por isso ele é frequentemente usado em provas de indecidibilidade.

Definição do Problema

A entrada do problema consiste em duas listas finitas $\alpha _{1},\ldots ,\alpha _{N}$ e $\beta _{1},\ldots ,\beta _{N}$ de palavras sobre algum alfabeto $A$ tendo pelo menos 2 símbolos. Uma solução para esse problema é uma sequência de índices $(i_{k})_{1\leq k\leq K}$ com $K\geq 1$ e $1\leq i_{k}\leq N$ para todo $k$ tal que

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

O problema de decisão é, então, decidir se tal solução existe ou não.

Exemplo de instâncias do Problema

Exemplo 1

Considere as duas listas seguintes:

α1 α2 α3 a ab bba

β1 β2 β3 baa aa bb

Uma solução para esse problema seria a sequência (3, 2, 3, 1) porque

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

além disso, desde que (3, 2, 3, 1) seja uma solução, então também é solução todas as suas "repetições", tais como (3, 2, 3, 1, 3, 2, 3, 1), etc.; Isso é, quando uma solução existe, existe mais infinitas soluções para esse tipo repetitivo.

Contudo, se duas listas consistissem de apenas $\alpha _{2},\alpha _{3}$ e $\beta _{2},\beta _{3}$, então não existiria solução ( porque então nenhum par correspondente teria a mesma ultima letra, como deve acontecer ao final de uma solução) Uma maneira conveniente de ver uma instância do problema de correspondência de Post é que dada uma coleção de blocos na forma:

αi βi

de tal forma que haja um suprimento ilimitado de cada tipo de bloco. Assim, o exemplo acima é visto como abaixo:

a baa	ab aa	bba bb
i = 1	i = 2	i = 3

Onde o "solucionador" tem um provimento infinito de cada um desses três tipos de blocos. Uma solução corresponde, de certa maneira, a colocar os blocos próximos uns dos outros de tal forma que a cadeia correspondente à célula de cima corresponda à cadeia na célula de baixo. Então a solução para o exemplo acima seria:

bba bb	ab aa	bba bb	a baa
i1 = 3	i2 = 2	i3 = 3	i4 = 1

Exemplo 2

Novamente, usando blocos para representar uma instância do problema, o problema seguinte é um exemplo de que existem infinitas soluções para o tipo obtido simplesmente "repetindo" uma solução.

bb b	ab ba	c bc
1	2	3

Nessa instância, cada sequência na forma (1, 2, 2, ..., 2, 3) é uma solução (além de todas as suas repetições):

bb b	ab ba	ab ba	ab ba	c bc
1	2	2	2	3

Esboço da prova de indecidibilidade

A maneira mais comum de se provar indecidibilidade de PCP descreve uma instância de PCP que pode simular uma computação em uma máquina de Turing com uma entrada particular. Uma correspondência somente irá ocorrer se a entrada for aceita pela máquina de Turing. Dado que saber se uma máquina de Turing irá aceitar uma entrada é um problema básico de indecidibilidade, PCP não pode ser decidível também. A discussão seguinte é baseada no livro de Michael Sipser, " Introdução a teoria da computação"..

Em mais detalhes, a idéia é que uma cadeia ao longo da parte superior e inferior seja um histórico de computação. Isso significa que isso irá listar uma cadeia descrevendo o estado inicial seguido de uma cadeia descrevendo o próximo estado e assim por diante até que seu fim seja uma cadeia descrevendo um estado de aceitação. As cadeias de estado são separadas por alguns símbolos (geralmente escritos como #). Segundo a definição de máquina de Turing, o estado completo de uma máquina consiste de 3 partes:

• O conteúdo atual da fita

• O estado atual da maquina de estado finita na qual opera o cabeçote da maquina

• A posição atual do cabeçote sobre a fita

Embora a fita tenha infinitas células, só alguns prefixos finitos destes serão do tipo não-brancos. Escrevemos esses abaixo como parte do nosso estado. Para descrever o estado de controle finito, nos criamos símbolos rotulados q₁ até q_k, para cada um dos "k" estados finitos da maquina. Nos inserimos o simbolo correto na cadeia descrevendo o conteúdo da fita na posição em que se encontra o cabeçote, indicando, assim, tanto a posição da cabeça da fita e do estado atual do controle finito. Para o alfabeto {1,0}, um estado típico poderia ser algo como:

101101110q₇00110.

Uma história da computação simples seria então algo do tipo:

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

Começamos com este bloco, onde "x" é a sequência de entrada e q₀ é o estado inicial:

q0x#

O topo começa "defasado" em relação a cadeia de baixo por um Estado, e mantém esta defasagem até a fase final. Em seguida, para cada símbolo do alfabeto da fita, bem como #, temos uma "cópia" do bloco, que copia o símbolo sem modificações de um estado para o outro:

a

a

Nos também temos um bloco para cada posição de transição que uma máquina pode fazer, mostrando como o cabeçote se move, como os estados finitos mudam e o que acontece com os estados circundantes. Por exemplo, aqui o cabeçote esta sobre um 0 no estado 4, e então escreve um 1 e move-se para a direita, mudando para o estado 7:

q40

1q7

Finalmente, quando o topo alcança o estado de aceitação, a parta inferior precisa de uma mudança para finalmente alcançar a correspondência completa. Para isso acontecer, nos precisamos estender a computação para que uma vez o estado de aceitação ser alcançado, cada passo subsequente da máquina irá causar a um simbolo próximo ao cabeçote que desapareça, um por vez até existir mais nenhum. Se q_f é um estado de aceitação, nos podemos representar isso com os seguintes blocos de transição, onde "a" é um símbolo do alfabeto da fita:

qfa qf

aqf qf

Há um bom número de detalhes a serem trabalhados, tais como lidar com limites entre estados, mas isso apenas mostra a idéia geral de como uma "charada" desse tipo pode simular uma computação da máquina de Turing.

Variantes

Muitas variantes do PCP têm sido consideradas. Uma razão é de que quando se tenta provar indecidibilidade de algum novo problema através da redução da PCP, muitas vezes acontece de uma primeira redução encontrada não ser PCP em si, mas de uma versão aparentemente mais fraca do PCP.

• A condição de que o alfabeto $A$ tem que ter pelo menos dois símbolos é exigido desde que o problema é decidível se $A$ tiver apenas um simbolo.

• Uma variante simples é fixar n, o número de "telhas". Este problema é decidível se n ≤ 2, mas permanece indecidível para n ≥ 7. É desconhecido se o problema é decidível para 3 ≤ n ≤ 6.

• O problema de correspondência circular de Post pergunta se índices $i_{1},i_{2},...$ podem ser encontrados tal que $\alpha _{i_{1}}\cdots \alpha _{i_{k}}$ e$\beta _{i_{1}}\cdots \beta _{i_{k}}$ são palavras conjugadas, ou seja, eles são iguais a rotação modulo. Esta variante é indecidível.

• Uma das variantes mais importantes do PCP é o problema de correspondência limitada de Post', que pergunta se podemos encontrar um jogo usando não mais do que k "telhas" , incluindo "azulejos" repetidos. A busca de força bruta resolve o problema em tempo O(2^k), mas isso pode ser difícil de melhorar, já que o problema é NP-completo. Ao contrário de alguns problemas NP-completos como o problema da satisfatibilidade booleana, uma pequena variação do problema delimitado também foi mostrado para ser completa para "RNP", o que significa que continua a ser difícil até mesmo se as entradas são escolhidas aleatoriamente (é difícil, em média, entradas distribuídas uniformemente).

• Outra variante do PCP é chamado o problema de correspondência marcada de Post, em que cada u_i deve-se começar com um símbolo diferente, e cada v_i também devem começar com um símbolo diferente.Halava, Hirvensalo, e De Wolf mostraram que esta variação é decidível em tempo exponencial. Além disso, eles mostraram que, se essa exigência é ligeiramente "frouxa" então que apenas os prefixos de dois caracteres precisem diferenciar-se (a chamada problema de correspondência Post 2-marcado), o problema torna-se indecidível novamente.

• O problema embutido de Post é outra variante em que se olha para os índices $i_{1},i_{2},...$ tal que $\alpha _{i_{1}}\cdots \alpha _{i_{k}}$ é uma sub-palavra(espalhada) de $\beta _{i_{1}}\cdots \beta _{i_{k}}$. Esta variante é facilmente decidível uma vez que, quando algumas soluções existem, em particular uma solução de tamanho um existe. Mais interessante é o problema embutido regular de Post, uma variante ainda mais além quando se olha para as soluções que pertencem a uma determinada linguagem regular (apresentado, por exemplo, sob a forma de uma expressão regular sobre o conjunto $\{1,...,N\}$). O problema embutido regular de Post ainda é decidível, mas, por causa da restrição adicional regular, ele tem uma complexidade muito alta que domina cada função de multiplicativa recursiva.

Ligações externas

• Eitan M. Gurari. An Introduction to the Theory of Computation, Chapter 4, Post's Correspondence Problem. A proof of the undecidability of PCP based on a generalization of context-free grammars.
• Online PHP Based PCP Solver
• PCP AT HOME