Finite Algebras with Hom-Sets of Polynomial Size

arXiv2307.06740MaRDI QIDQ6443643FDOQ6443643

Authors: Libor Barto, Antoine Mottet 

Publication date: 13 July 2023

Abstract: We provide an internal characterization of those finite algebras (i.e., algebraic structures) $mathbfA$ such that the number of homomorphisms from any finite algebra $mathbfX$ to $mathbfA$ is bounded from above by a polynomial in the size of $mathbfX$. Namely, an algebra $mathbfA$ has this property if, and only if, no subalgebra of $mathbfA$ has a nontrivial strongly abelian congruence. We also show that the property can be decided in polynomial time for algebras in finite signatures. Moreover, if $mathbfA$ is such an algebra, the set of all homomorphisms from $mathbfX$ to $mathbfA$ can be computed in polynomial time given $mathbfX$ as input. As an application of our results to the field of computational complexity, we characterize inherently tractable constraint satisfaction problems over fixed finite structures, i.e., those that are tractable and remain tractable after expanding the fixed structure by arbitrary relations or functions.

Mathematics Subject Classification ID

Other classes of algebras (08C99)

This page was built for publication: Finite Algebras with Hom-Sets of Polynomial Size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443643)