Decida a existência de um homomorfismo de cordas

Considere o seguinte problema:

Dadas duas cadeias x, y, decida se existe um homomorfismo da cadeia f tal que f (x) = y.

É fácil mostrar que este problema está em . Há outras coisas que podemos dizer sobre esse problema? É por exemplo em C O N P , ou mesmo P ?$NP$$coNP$$P$

Esse problema parece muito natural, portanto, não me surpreendo se ele tiver sido estudado minuciosamente. No entanto, não pude encontrar esse problema na literatura.

É discutido em um dos primeiros trabalhos sobre strings e complexidade, a saber, Dana Angluin, Encontrando padrões comuns a um conjunto de strings, J. Comput. Sci do sistema 21 (1980), 46-62. Veja o teorema 3.6. O problema é NP-completo.

Também está em A. Ehrenfeucht, G. Rozenberg, Encontrar um homomorfismo entre duas palavras é NP-completo, Inform. Processo. Lett. 9 (1979) 86-88.