The Complexity of Homomorphism Factorization
From MaRDI portal
Equational classes, universal algebra in model theory (03C05) Model theory of finite structures (03C13) Structure theory of algebraic structures (08A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
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 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 from X to Y and h from Y to Z such that f = hg. We show that these Homomorphism Factorization Problems are NP-complete. We also develop a technique for producing compatible restrictions on homomorphisms, and show that Homomorphism Factorization Problems have polynomial time instances for finite Boolean algebras, finite vector spaces, finite G-sets, and finite abelian groups.
This page was built for publication: The Complexity of Homomorphism Factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6312097)
