A subscription is required to access this article.
We show that every finite algebra which is finitely related and lies in a congruence modular variety has few subpowers. This result, combined with other theorems, has interesting consequences for the complexity of several computational problems associated to finite relational structures: the constraint satisfaction problem, the primitive positive formula comparison problem, and the learnability problem for primitive positive formulas. Another corollary is that it is decidable whether an algebra given by a set of relations has few subpowers.
Cite this article
Libor Barto, Finitely related algebras in congruence modular varieties have few subpowers. J. Eur. Math. Soc. 20 (2018), no. 6, pp. 1439–1471DOI 10.4171/JEMS/790