Zdecyduj o istnieniu homomorfizmu strun

Rozważ następujący problem:

Biorąc pod uwagę dwa ciągi x, y, zdecyduj, czy istnieje homomorfizm ciągu f taki, że f (x) = y.

Łatwo jest pokazać, że problem ten jest w . Czy są inne rzeczy, które możemy powiedzieć o tym problemie? Jest to na przykład w c o N P lub nawet P ?$NP$$coNP$$P$

Ten problem wydaje się bardzo naturalny, więc nie jestem zaskoczony, jeśli został dokładnie zbadany. Jednak nie mogłem znaleźć tego problemu w literaturze.

Jest to omówione w jednym z pierwszych artykułów na temat łańcuchów i złożoności, a mianowicie Dana Angluin, Znalezienie wzorców wspólnych dla zestawu łańcuchów, J. Comput. System Sci. 21 (1980), 46–62. Spójrz na Twierdzenie 3.6. Problem jest NP-zupełny.

Jest również w A. Ehrenfeucht, G. Rozenberg, Znalezienie homomorfizmu między dwoma słowami jest NP-zupełne, Inform. Proces. Łotysz. 9 (1979) 86–88.