8
$\begingroup$

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?

$\endgroup$
  • 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/python-constraint. I don't know if it is good or not though. $\endgroup$ – Joseph Van Name Mar 22 '17 at 0:08
6
$\begingroup$

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

| cite | improve this answer | |
$\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.