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.

Included in

Mathematics Commons

Share

COinS