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?

Improve this question
$\endgroup$
2
  • 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
    Commented Feb 11, 2017 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
    Commented Mar 22, 2017 at 0:08

1 Answer 1

Reset to default
7
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .