Tutorial
Algebra and Logic in the Complexity of Constraints
On-site
What kind of mathematical structure in computational problems allows for efficient algorithms? This fundamental question now has a satisfactory answer for a rather broad class of computational problems, so called fixed-template finite-domain Constraint Satisfaction Problems (CSPs). This answer, due to Bulatov and Zhuk, stems from the interplay between algebra and logic, similar to the classical connection between permutation groups and first-order definability.
Th aim of this tutorial is to explain this algebra-logic interplay, show how it is applied in CSPs, and discuss some of the major research directions.
This document was translated from LATEX by HEVEA.