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 NPcomplete problem? Is this problem still NPcomplete when all operations are associative?

3$\begingroup$ The name Agnes Szendrei pops to mind. Though it may be someone else who did the work, I think she was involved in computer search and enumeration of morphisms (whether iso, hom, or endomorphisms I don't remember). You might search such work within the last twenty years for the program her team used. Gerhard "Sorry I Don't Remember More" Paseman, 2017.02.11. $\endgroup$ – Gerhard Paseman Feb 11 '17 at 19:23

$\begingroup$ I found this software labix.org/pythonconstraint. I don't know if it is good or not though. $\endgroup$ – Joseph Van Name Mar 22 '17 at 0:08
I mentioned this problem to one of my students, Kevin Berg, who proved that this homomorphism factorization problem is NPcomplete 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 NPcomplete when restricted to algebras with one associative binary operation (i.e. for semigroups). His arxiv preprint is here: