Let $(X,*),(Y,*),(Z,*)$ be finite algebras. The binary operations $*$ are not required to satisfy any identities though I am interested in the special case where $*$ is associative. Suppose that $f:X\rightarrow Z,g:Y\rightarrow Z$ are homomorphisms. Then is there already an optimized computer program that searches for homomorphisms $\phi:X\rightarrow Y$ where $g\circ\phi=f$? Is the problem of finding such a homomorphism $\phi$ an NP-complete problem? Is this problem still NP-complete when all operations are associative?
I mentioned this problem to one of my students, Kevin Berg, who proved that this homomorphism factorization problem is NP-complete when considered for the class of all finite algebras in a language containing at least 2 unary operations or containing at least one operation of arity at least 2. He also proved that the problem remains NP-complete when restricted to algebras with one associative binary operation (i.e. for semigroups). His arxiv preprint is here: