ON THE COMPLEXITY OF DECIDING HOMOMORPHISM-HOMOGENEITY FOR FINITE ALGEBRAS

In 2006, Cameron and Nešetřil introduced the following variant of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finitely generated substructures of the structure extends to an endomorphism of the structure. In several recent papers homomorphism-homogeneous objects in some well-known classes of algebras have been described (e.g. monounary algebras and lattices), while finite homomorphism-homogeneous groups were described in 1979 under the name of finite quasi-injective groups. In this paper we show that, in general, deciding homomorphism-homogeneity for finite algebras with finitely many fundamental operations and with at least one at least binary fundamental operation is coNP-complete. Therefore, unless P = coNP, there is no feasible characterization of finite homomorphism-homogeneous algebras of this kind.