Entscheiden Sie, ob ein String-Homomorphismus vorliegt

Betrachten Sie das folgende Problem:

Entscheiden Sie bei zwei Strings x, y, ob ein String-Homomorphismus f existiert, so dass f (x) = y ist.

Es ist leicht zu zeigen, dass dieses Problem in . Gibt es noch andere Dinge, die wir zu diesem Problem sagen können? zB Ist es in c o N P oder sogar P ?$NP$$coNP$$P$

Dieses Problem scheint sehr natürlich zu sein, daher wundert es mich nicht, wenn es gründlich untersucht wurde. Dieses Problem konnte ich jedoch in der Literatur nicht finden.

Es wird in einem der allerersten Artikel über Zeichenfolgen und Komplexität diskutiert, nämlich Dana Angluin, Finden von Mustern, die einer Reihe von Zeichenfolgen gemeinsam sind, J. Comput. System Sci. 21 (1980), 46-62. Schauen Sie sich Satz 3.6 an. Das Problem ist NP-vollständig.

Es ist auch in A. Ehrenfeucht, G. Rozenberg, einen Homomorphismus zwischen zwei Wörtern zu finden, ist NP-vollständig, Inform. Prozess. Lette. 9 (1979) 86–88.