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

Rings and Algebras