<p>It's discussed in one of the very first papers about strings and complexity, namely, Dana Angluin, Finding patterns common to a set of strings, J. Comput. System Sci.
21 (1980), 46-62.  Look at Theorem 3.6.  The problem is NP-complete.</p>

<p>It's also in A. Ehrenfeucht, G. Rozenberg, Finding a homomorphism between two words is NP-complete, Inform. Process. Lett. 9 (1979) 86–88.</p>

CC BY-SA 3.0
2014-11-08T17:38:52.917Z
2014-11-08T20:24:37.187Z
2014-11-08T20:24:37.187Z
Jeffrey Shallit
<p>Consider the following problem:</p>

<blockquote>
  <p>Given two strings x,y, decide whether there exists a string homomorphism f such that f(x)=y.</p>
</blockquote>

<p>It is easy to show that this problem is in $NP$. Are there other things we can say about this problem? e.g. Is it in $coNP$, or even $P$?</p>

<p>This problem seems very natural, so I am not surprised if it has been studied thoroughly. However I could not find this problem in literature.</p>

<cc.complexity-theory><reference-request><fl.formal-languages>
Decide the existence of a string homomorphism
Yuzhou Gu
# Decide the existence of a string homomorphism

(Asked by: username_0 on 2014-11-08)

Consider the following problem:

> Given two strings x,y, decide whether there exists a string homomorphism f such that f(x)=y.

It is easy to show that this problem is in $NP$. Are there other things we can say about this problem? e.g. Is it in $coNP$, or even $P$?

This problem seems very natural, so I am not surprised if it has been studied thoroughly. However I could not find this problem in literature.

**Tags:** cc.complexity-theory, reference-request, fl.formal-languages


---

## 1 answers

### Answer by username_1 on 2014-11-08. Score: 16 | Accepted answer

It's discussed in one of the very first papers about strings and complexity, namely, Dana Angluin, Finding patterns common to a set of strings, J. Comput. System Sci.
21 (1980), 46-62. Look at Theorem 3.6. The problem is NP-complete.

It's also in A. Ehrenfeucht, G. Rozenberg, Finding a homomorphism between two words is NP-complete, Inform. Process. Lett. 9 (1979) 86–88.


---

