Date of Award
Doctor of Philosophy (PhD)
Keith A. Kearnes
We investigate the computational complexity of the problem of deciding if an algebra homomorphism can be factored through an intermediate algebra. Specifically, we fix an algebraic language, L, and take as input an algebra homomorphism f: X --> Z between two finite L-algebras X and Z, along with an intermediate finite L-algebra Y. The decision problem asks whether there are homomorphisms g: X --> Y and h: Y --> Z such that f=hg. We show that this problem is NP-complete for most languages. We also investigate special cases where homomorphism factorization can be performed in polynomial time.
Berg, Kevin Michael, "The Complexity of Homomorphism Factorization" (2019). Mathematics Graduate Theses & Dissertations. 73.