Algebraic approach to constraint satisfaction

Remarks

The approach rests on a reduction principle. If $\mathbb{A}$ and $\mathbb{B}$ share the universe $A$ and $\operatorname{Pol}(\mathbb{A}) \subseteq \operatorname{Pol}(\mathbb{B})$, then $\operatorname{CSP}(\mathbb{B})$ reduces to $\operatorname{CSP}(\mathbb{A})$ in polynomial time. The reason is that each relation of $\mathbb{B}$ is then primitive positive definable from $\mathbb{A}$, by the Pol–Inv Galois connection. Example: for the complete graph $K_2$, $\operatorname{CSP}(K_2)$ asks whether a graph is $2$-colourable, as a graph homomorphism to $K_2$. The majority operation on $\set{0, 1}$ is a polymorphism of the edge relation $\set{(0, 1), (1, 0)}$, and the problem is in polynomial time. Non-example of tractability: every polymorphism of $K_3$ has the form $\sigma(x_i)$ for a permutation $\sigma$ of $\set{0, 1, 2}$. So $K_3$ has no Taylor polymorphism, and $3$-colouring is NP-complete.