restrictions décidables de la poste Correspondance problème

Question

Le Poster Correspondance problème (PCP) est indécidable.

Version limitée du PCP est $ \ mathrm {NP} $ - complète et version annotée du PCP (les mots de l'un des deux listes sont nécessaire pour différer la première lettre) est en $ \ mathrm {} PSPACE $ [1].

1. Est-ce que ces versions limitées utilisées pour prouver des résultats de la complexité des autres problèmes (par la réduction)?
2. Y at-il d'autres versions restreintes du PCP qui en font décidable (et en $ particulier \ mathrm {PSPACE} $ - complet)?

[1] " PCP marqué est décidable " par V. Halava, M. Hirvensalo, R. De Wolf (1999)

Answer 1

il y a plus d'une façon de « lié » PCP (frisant peut-être sur un grand nombre!) Et il semble y avoir diverses recherches dans de nombreuses variantes. limiter le nombre de blocs concaténés ou longueur totale des chaînes concaténées à un paramètre spécifié sur l'entrée (spécifiée en binaire) semble être NExpSpace complet, mais ne l'ont pas vu cette écrit dans un document. voir Borné Poster Correspondance problème NP-complet Preuve , tcs. elle-même. si vous limitez le même paramètre « longueur de concaténation » à un polynôme de la taille d'entrée de son apparence PSpace complète. nouveau havent vu que rédigé partout malgré une certaine recherche.

il y a aussi la recherche un peu connexes dans la résolution des cas particuliers du PCP (un peu penser à la recherche Castors), voir par exemple solveur PCP par Zhao et [8]. A noter que Theres aussi un cas remarquable / pionnier de l'application de l'ADN de calcul pour une approche quelque peu probabiliste. [3] aussi il semble y avoir plus de recherche par Halava [4], [7] dans d'autres variantes décidables. [5,6] sont d'autres résultats misc.

[1] Tackling Messages problème de correspondance par Zhao (v2)

[2] Un polynôme la réduction de tout problème NP-complet au PCP borné , cs.se

[3] En utilisant l'ADN pour résoudre le message borné Correspondance problème par Kari et al

[4] sur Post Correspondance problème pour Lettre monotones Langues par Halava et al

[5] Le problème de correspondance post sur un alphabet unaire par Rudnicki

[6] Poster Correspondance problème Partiellement commutative Alphabets Barbara Klunder, Wojciech Rytter

[7] Quelques nouveaux résultats sur Post Correspondance problème et son Modifications par Halava, Harju

[8] Création d'instances difficiles du message Correspondance problème par Lorentz

Answer 2

Ehrenfeucht, Karhumäki et Rozenberg ont montré que la PCP binaire (où le domaine est binaire) est décidable. Halava et Holub plus tard a montré que c'est en fait dans P.