tutorial notes

12 Aug 2026

Algebraic approach to constraint satisfaction

link to slides

main theorem
If there is a natural transformation $\operatorname{pol}(A) \to \operatorname{pol}(B)$ then $\operatorname{CSP}(B)$ reduces to $\operatorname{CSP}(A)$ in logspace.

I recommend these two papers as an entry point into the theory. The first is recommended to anyone who knows what a functor is, and provides a categorical treatment of the above theorem. The second is more tradional. It was written for combinatorists, and provides a good overview of the state-of-the-art of the field just before the resolution of the dichotomy conjecture.

  1. Jakl, T., Hadek, M., Opršal, J. (2026). A categorical perspective on constraint satisfaction: The wonderland of adjunctions. 41st Annual Symposium on Logic in Computer Science, LICS 2026, (pp. 54:1-54:27). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. arXiv:2503.10353. doi:10.4230/LIPIcs.LICS.2026.54
  2. Barto, L., Krokhin, A., Willard, R. (2017). Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7 (pp. 1–44). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/DFU.Vol7.15301.1

exercises

  1. Prove that $\operatorname{pol}(\operatorname{HornSAT})$ is naturally equivalent to the powerset functor on $\operatorname{Fin}$.

  2. Given $M \colon \operatorname{Fin} \to \operatorname{Fin}$, describe $\operatorname{pol}(\operatorname{Id}, M)$.

  3. Show that $B^* \circ \operatorname{Lan}_A$ is computable in logspace (where $B^*(M) = M \circ B$).

  4. Given a natural number $n > 2$, show that solving systems of linear equations mod $n$ is NP-hard if we allow a non-linear (optional) constraint $x \in {0, 1}$.

References