#### Date of Award

Spring 1-1-2019

#### Document Type

Dissertation

#### Degree Name

Doctor of Philosophy (PhD)

#### First Advisor

Keith A. Kearnes

#### Second Advisor

William DeMeo

#### Third Advisor

Peter Mayr

#### Fourth Advisor

Nikola Ruskuc

#### Fifth Advisor

Agnes Szendrei

#### 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.

#### Recommended Citation

Berg, Kevin Michael, "The Complexity of Homomorphism Factorization" (2019). *Mathematics Graduate Theses & Dissertations*. 73.

https://scholar.colorado.edu/math_gradetds/73