Finitely related algebras in congruence modular varieties have few subpowers

Abstrakt

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.

Klíčová slova

• Finitely related algebra
• congruence modular variety
• Gumm terms
• few subpowers
• cube terms