Acabei de ler algumas páginas do livro de Sipser Introdução à teoria da computação sobre o problema pós-correspondência, e estou pensando que o PCP está realmente em NP. O certificador é: para uma configuração de entrada da pilha concatenando como uma string concatenando como uma cadeia de , e depois comparar e para ver se os dois são iguais e, em seguida, concluir que a entrada é, na verdade, uma solução de PCP.
complexity-theory
decision-problem
np
phhoang
fonte
fonte
Respostas:
O problema da correspondência posterior é indecidível e, em particular, não está no NP. A razão pela qual sua ideia não funciona é que a testemunha não é necessariamente do tamanho polinomial (na verdade, você acabou de provar). Ou seja, para que seu certificador prove que o problema de pós-correspondência está no NP, ele precisa ser executado em tempo polinomial (em termos do tamanho da instância do PCP ). Acontece que, neste caso, nem sempre há uma solução de tamanho polinomial, mesmo quando o problema é solucionável. De fato, não há limite computável para o tamanho de uma solução em potencial, pois, caso contrário, o problema seria decidível!
fonte
Sua testemunha é polinomial no tamanho da solução e não no tamanho da entrada. Você não tem como limitar o tamanho das possíveis soluções. Sua prova mostra que o PCP é recursivamente enumerável.
fonte