Options
Finite algebras with hom-sets of polynomal size
Publikationstyp
Journal Article
Date Issued
2024-10-24
Sprache
English
Volume
378
Issue
1
Start Page
569
End Page
596
Citation
Transactions of the American Mathematical Society 378 (1): 569-596 (2025)
Publisher DOI
Scopus ID
Publisher
American Mathematical Soc.
We provide an internal characterization of those finite algebras (i.e., algebraic structures) A such that the number of homomorphisms from any finite algebra X to A is bounded from above by a polynomial in the size of X. Namely, an algebra A has this property if, and only if, no subalgebra of A 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 A is such an algebra, the set of all homomorphisms from X to A can be computed in polynomial time given X 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.
DDC Class
510: Mathematics