11
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.