¿Es el problema posterior a la correspondencia en NP?

12

Acabo de leer algunas páginas en el libro de Sipser Introducción a la teoría de la computación sobre el problema posterior a la correspondencia, y estoy pensando que PCP está realmente en NP. El certificador es: para una configuración de entrada de pile concatenando como una cadena y concatenando como una cadena , luego compare y para ver si los dos son iguales y luego concluya que la entrada es en realidad una solución para PCP.

(t1/b1,t2/b2,...tn/bn)
t1,t2,...,tntb1,b2,...,bnbtb
phhoang
fuente
2
a / la versión limitada / variante de este problema es NP completa. ver, por ejemplo, PCP NP acotado completo / Ciencias de la Computación Teórica
vzn

Respuestas:

19

El problema de la correspondencia Post es indecidible, y en particular es no en NP. La razón por la que su idea no funciona es que el testigo no es necesariamente de tamaño polinómico (de hecho, lo acaba de probar). Es decir, para que su certificador demuestre que el problema de la correspondencia posterior está en NP, debe ejecutarse en tiempo polinómico (en términos del tamaño de la instancia de PCP ). Resulta que en este caso no siempre hay una solución de tamaño polinómico, incluso cuando el problema es solucionable. De hecho, no hay límite computable en el tamaño de una solución potencial, ya que de lo contrario el problema sería decidible.

Yuval Filmus
fuente
11

Su testigo es polinómico en el tamaño de la solución, no en el tamaño de la entrada. No tiene forma de limitar la longitud de las posibles soluciones. Su prueba muestra que PCP es recursivamente enumerable.

phs
fuente