O Problema Pós Correspondência (PCP) é indecidível.
A versão limitada do PCP é -completa e a versão marcada do PCP (as palavras de uma das duas listas devem diferir na primeira letra) está em [1].
[1] " PCP marcado é decidível " por V. Halava, M. Hirvensalo, R. De Wolf (1999)
existe mais de uma maneira de "vincular" o PCP (talvez quase em muitos!) e parece haver uma pesquisa diversificada em muitas variantes. limitar o número de blocos concatenados ou o comprimento total de seqüências concatenadas a um parâmetro especificado na entrada (especificado em binário) parece estar completo com o NExpSpace, mas isso não foi registrado em um documento. consulte Prova do problema NP-Complete de correspondência limitada , tcs.se. se você limitar o mesmo parâmetro "comprimento da concatenação" a um polinômio do tamanho da entrada, seu PSpace aparentemente estará completo. novamente não vi isso escrito em nenhum lugar, apesar de algumas pesquisas.
também há pesquisas relacionadas à resolução de casos especiais do PCP (um pouco remanescente da pesquisa do Busy Beaver), veja, por exemplo, o solucionador de PCP de Zhao ou [8]. note que também há um caso notável / pioneiro de aplicar a computação de DNA para uma abordagem um tanto probabilística. [3] também parece haver mais pesquisas de Halava [4], [7] em outras variantes decidíveis. [5,6] são outros resultados diversos.
[1] Abordando o problema de correspondência de Zhao (v2?)
[2] Uma redução polinomial de qualquer problema completo de NP para PCP limitado , cs.se
[3] Usando o DNA para resolver o problema da correspondência pós encadernada por Kari et al.
[4] Problema pós-correspondência para idiomas monotônicos de letras de Halava et al.
[5] O problema da correspondência de Post sobre um alfabeto unário de Rudnicki
[6] Problema pós-correspondência com alfabetos parcialmente comutativos Barbara Klunder, Wojciech Rytter
[7] Alguns novos resultados sobre o problema pós-correspondência e suas modificações por Halava, Harju
[8] Criando instâncias difíceis do problema de correspondência posterior de Lorentz
Ehrenfeucht, Karhumäki e Rozenberg mostraram que o PCP binário (onde o domínio é binário) é decidível. Halava e Holub mais tarde mostraram que está realmente em P.