Finite algebras with Hom-sets of polynomial size

We provide an internal characterization of those finite algebras (i. e. , algebraic structures) A A such that the number of homomorphisms from any finite algebra X X to A A is bounded from above by a polynomial in the size of X X. Namely, an algebra A A has this property if, and only if, no subalgebra of A 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 A is such an algebra, the set of all homomorphisms from X X to A A can be computed in polynomial time given X 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.