Minicourse on CSP - Talk 1 - Constraint Satisfaction Problems: Introduction and the Universal-Algebraic Approach

An instance of the constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, if there is an assignment to the variables satisfying all of the constraints. Instances of the CSP can be found in many fields such as artificial intelligence, temporal and spatial reasoning, database theory, graph theory, and algebra. Recent years have seen a research focus on understanding which so-called constraint languages can be solved efficiently (in polynomial time), and which are inherently intractable (NP-hard). This focus has arisen in large part due to a new method for studying constraint languages based on universal algebra, presented in the 90s. In this talk, we aim to give a self-contained introduction to constraint satisfaction problems and the universal algebraic approach to studying them. This will be something of a tutorial-style talk in two parts: the first part will be a gentle introduction to constraint satisfaction in which I plan to discuss and relate different formulations of the CSP, and discuss restricting the CSP based on the constraint language; the second part will present the basic logical and algebraic concepts used to understand the complexity of the CSP.