Applications of algebra to the study of fine-grained computational complexity of constraint satisfaction problems

在约束满足问题(CSP)中，必须指定 必须满足各种约束的变量的值；典型的 现实世界的例子包括调度问题、数据库查询、 图像处理和频率分配问题。总体而言, 确定CSP是否接受解决方案是一种算法 挑战，但在实践中经常发生的是限制 是一种非常受限的形式，允许使用高效 方法求解CSP问题。我们的长期目标是将 究竟是什么样的限制导致了这些可驯服的 CSP的。我们的方法是基于意想不到的和富有成效的 已发现的CSP与普适代数的联系 在90年代末，P·吉文斯的《S》。简而言之，每一个家庭 约束被转换为数学对象，其 代数性质在某种程度上反映了解决 CSP.这种代数方法导致了一些重大突破 在过去的10年里，在对算法复杂性的研究中 约束满足问题。

In a constraint satisfaction problem (CSP), one must assign values to variables that must satisfy various constraints; typical real world examples include scheduling problems, database queries, image-processing, and frequency assignment problems. 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. This algebraic approach has led to some major breakthroughs in the last 10 years in the study of the algorithmic complexity of constraint satisfaction problems.