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?



Is there a good computer program for searching for endomorphisms between finite algebras which make diagrams commute? Is this problem NP-complete?
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:


[The Complexity of Homomorphism Factorization](https://arxiv.org/abs/1901.01817)


