Tractable constraint languages arising from some algebras that generate congruence distributive varieties
Seminar Room 1, Newton Institute
A consequence of conjectures of Larose-Zadori and of Bulatov is that any constraint language arising from a finite algebra that generates a congruence distributive variety is of bounded relational width and hence is tractable. Some special cases of this have been known for some time, for example, when the algebra has a majority or, more generally, a near unanimity term operation.
A classic theorem of universal algebra (due to Jonsson) is that an algebra generates a congruence distributive variety if and only if it has a sequence of Jonsson terms. In my talk I will discuss the following theorem, produced with Emil Kiss:
Theorem: Let A be a finite algebra that has a sequence of four Jonsson terms. Then the infinite constraint language consisting of all subuniverses of finite powers of A has bounded relational width and hence is globally tractable.