Y a-t-il un problème de post-correspondance dans NP?

Je viens de lire quelques pages du livre de Sipser Introduction à la théorie du calcul sur le problème de la correspondance postérieure, et je pense que PCP est en fait dans NP. Le certificateur est la suivante : pour une configuration de pile d'entrée concaténer t 1 , t 2 , . . . , t n comme une chaîne t et concaténant b 1 ,

$$(t_1/b_1, t_2/b_2,...t_n/b_n)$$ $t_1, t_2,...,t_n$$t$ sous la forme d'une chaîne b , puis comparez t et b pour voir si les deux sont égaux, puis concluez que l'entrée est en fait une solution au PCP.$b_1, b_2, ..., b_n$$b$$t$$b$

Le problème de la correspondance par correspondance est indécidable, et en particulier il n'est pas dans NP. La raison pour laquelle votre idée ne fonctionne pas est que le témoin n'est pas nécessairement de taille polynomiale (en fait, vous venez de le prouver). C'est-à-dire que pour que votre certificateur prouve que le problème de Post-correspondance est en NP, il doit s'exécuter en temps polynomial (en termes de taille de l' instance PCP ). Il s'avère que dans ce cas, il n'y a pas toujours de solution de taille polynomiale même lorsque le problème est résoluble. En fait, il n'y a pas de limite calculable sur la taille d'une solution potentielle, car sinon le problème serait décidable!

Votre témoin est polynomial quant à la taille de la solution et non à la taille de l'entrée. Vous n'avez aucun moyen de limiter la longueur des solutions potentielles. Votre preuve montre que PCP est récursivement énumérable.