Finitely Related Algebras in Congruence Distributive Varieties Have Near Unanimity Terms

Abstract

We show that every finite, finitely related algebra in a congruence distributive variety has a near unanimity term operation. As a consequence we solve the near unanimity problem for relational structures: it is decidable whether a given finite set of relations on a finite set admits a compatible near unanimity operation.

This consequence also implies that it is decidable whether a given finite constraint language defines a constraint satisfaction problem of bounded strict width.

Keywords

• congruence distributive variety
• Jonsson operations
• near unanimity operation
• finitely related algebra
• constraint satisfaction problem