The Complexity of Homomorphism Factorization

Graduate Thesis Or Dissertation

Citations

Citeable URL: https://scholar.colorado.edu/concern/graduate_thesis_or_dissertations/x633f104m

Abstract

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.

Creator