Applications of algebra and topology to constraint satisfaction problems

在约束满足问题（CSP）中，必须对必须服从各种约束的变量赋值；典型的现实示例包括调度问题和数据库查询。一般来说，确定CSP是否允许解决方案是一个算法挑战，但在实践中经常发生约束形式非常受限的情况，从而允许使用有效的方法来解决CSP。我们的长期目标是精确分类哪些限制导致了这些可处理的CSP。我们的方法是基于在90年代末由P. Jeavons发现的CSP和通用代数之间意想不到的和富有成效的联系。简而言之，每个约束族都被转换成一个数学对象，其代数性质在某种程度上反映了求解CSP的难度。进一步借鉴了代数拓扑领域的方法来分析这些代数对象。这种代数方法在过去5年中在约束满足问题的算法复杂度研究方面取得了一些重大突破。

In a constraint satisfaction problem (CSP), one must assign values to variables that must obey various constraints; typical real world examples include scheduling problems and database queries. In general, determining whether a CSP admits a solution is an algorithmic challenge, but it often happens in practice that the constraints are of a very restricted form, allowing the use of efficient methods to solve the CSP. Our long-term goal is to classify precisely what kinds of restrictions lead to these tractable CSP's. Our approach is based on an unexpected and fruitful connection between CSP's and universal algebra that was uncovered in the late 90's by P. Jeavons. In short, every family of constraints is transformed into a mathematical object whose algebraic properties somehow reflect the difficulty of solving the CSP. Further methods borrowed from the field of algebraic topology are used to analyse these algebraic objects. This algebraic approach has led to some major breakthroughs in the last 5 years in the study of the algorithmic complexity of constraint satisfaction problems.