Finitely related algebras in congruence modular varieties have few subpowers

  • Libor Barto

    Charles University, Prague, Czechia

Abstract

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–1471

DOI 10.4171/JEMS/790