Constraint Satisfaction Problems: algebraic and model-theoretic challenges to distinguish the easy from the hard

Abstract

I will give a gentle introduction to current algebraic and model-theoretic methods in the computational complexity of Constraint Satisfaction Problems (CSPs). A CSP is a computational problem where we are given variables and constraints about them; the question is whether the variables can be assigned values such that all constraints are satisfied. Numerous natural computational problems, such as satisfiability of a given system of equations over a field, are CSPs; in fact, any computational problem is Turing-equivalent to a CSP. Any CSP can be modeled by a relational structure, and conversely every relational structure naturally defines a CSP. In view of humanity’s continuing quest to distinguish easy from hard problems in general, and the class P (polynomial-time solvable problems, e.g. satisfiability of linear equations over a field) from the class NP (polynomial-time verifiable problems, e.g. satisfiability of a propositional formula) in particular, the question arises which mathematical properties of a relational structure make the corresponding CSP easy and which make it hard. It turns out that particular algebraic invariants of the structure often determine the borderline between different complexity classes. Hence algebraic methods, combined with concepts from model theory as well as from Ramsey theory in the case of infinite structures, yield appropriate tools to determine the computational complexity of CSPs.