hay más de una forma de "vincular" a la PCP (¡tal vez raya en muchas!) y parece haber una investigación diversa en muchas variantes. limitar el número de bloques concatenados o la longitud total de las cadenas concatenadas a un parámetro especificado en la entrada (especificado en binario) parece ser NExpSpace completo, pero no lo he visto escrito en un documento. ver Problema de correspondencia posterior al límite Prueba completa de NP , tcs.se. si limita el mismo parámetro de "longitud de concatenación" a un polinomio del tamaño de entrada, aparentemente su PSpace está completo. de nuevo no he visto eso escrito en ninguna parte a pesar de alguna búsqueda.
También existe una investigación algo relacionada para resolver casos especiales de PCP (algo que recuerda a la investigación de Busy Beaver), ver, por ejemplo, PCP solucionador de Zhao o [8]. tenga en cuenta que también hay un caso notable / pionero de aplicar la computación de ADN para un enfoque algo probabilístico. [3] También parece haber más investigación por parte de Halava [4], [7] sobre otras variantes decidibles. [5,6] son resultados misceláneos adicionales.
[1] Problema de correspondencia de Tackling Posts por Zhao (v2?)
[2] Una reducción polinómica de cualquier problema NP-completo a PCP limitado , cs.se
[3] Utilizando el ADN para resolver el problema de la correspondencia posterior a los límites de Kari et al.
[4] Sobre el problema de correspondencia posterior a las lenguas monótonas de letras por Halava et al.
[5] El problema de correspondencia de Post sobre un alfabeto unario por Rudnicki
[6] Problema posterior a la correspondencia con alfabetos parcialmente conmutativos
Barbara Klunder, Wojciech Rytter
[7] Algunos resultados nuevos sobre el problema posterior a la correspondencia y sus modificaciones por Halava, Harju
[8] Creación de instancias difíciles del problema de correspondencia posterior por Lorentz
