Restrictions décidables du problème de correspondance postérieure

Le problème post-correspondance (PCP) est indécidable.

La version limitée du PCP est complète et la version marquée du PCP (les mots de l'une des deux listes doivent différer dans la première lettre) est en P S P A C E [1].$\mathrm{NP}$$\mathrm{PSPACE}$

1. Ces versions restreintes sont-elles utilisées pour prouver certains résultats de complexité d'autres problèmes (par réduction)?
2. Existe-t-il d'autres versions restreintes du PCP qui le rendent décidable (et en particulier -complete)?$\mathrm{PSPACE}$

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

il y a plus d'une façon de «lier» le PCP (peut-être à plusieurs!) et il semble y avoir diverses recherches sur de nombreuses variantes. Limiter le nombre de blocs concaténés ou la longueur totale des chaînes concaténées à un paramètre spécifié sur l'entrée (spécifié en binaire) semble être NExpSpace complet mais n'a pas vu cela écrit dans un document. voir Bounded Post Correspondence Problem NP-Complete Proof , tcs.se. si vous limitez le même paramètre "longueur de concaténation" à un polynôme de la taille d'entrée, son PSpace est apparemment complet. encore une fois, je n'ai vu cela écrit nulle part malgré quelques recherches.

il existe également des recherches quelque peu apparentées sur la résolution de cas particuliers du PCP (rappelant quelque peu la recherche de Busy Beaver), voir par exemple le solveur PCP de Zhao ou [8]. notons qu'il existe également un cas remarquable / pionnier d'application de l'informatique ADN pour une approche quelque peu probabiliste. il semble également y avoir plus de recherches par Halava [4], [7] sur d'autres variantes décidables. [5,6] sont d'autres résultats divers.

[1] Tackling Posts correspondence problem by Zhao (v2?)

[2] Une réduction polynomiale de tout problème NP-complet au PCP borné , cs.se

[3] Utiliser l'ADN pour résoudre le problème de la correspondance post-bornée par Kari et al

[4] On Post Correspondence Problem for Letter Monotonic Languages par Halava et al

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

[6] Problème de correspondance avec les alphabets partiellement commutables Barbara Klunder, Wojciech Rytter

[7] Quelques nouveaux résultats sur le problème de la correspondance postérieure et ses modifications par Halava, Harju

[8] Création d'instances difficiles du problème de la correspondance postérieure par Lorentz

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