Refined complexity of constraint satisfaction problems

在约束满足问题（CSP）中，必须对必须满足各种约束的变量赋值；典型的实际示例包括调度问题、数据库查询、图像处理和频率分配问题。一般来说，确定CSP是否允许解决方案是一个算法挑战，但在实践中经常发生约束形式非常受限的情况，从而允许使用有效的方法来解决CSP。我们的长期目标是精确分类哪些限制导致了这些可处理的CSP。我们的方法是基于在90年代末发现的CSP和通用代数之间意想不到的和富有成效的联系，这使得我们在过去20年里对CSP复杂性的理解取得了重大突破。简而言之，将每个约束族转化为数学对象，其代数性质反映了求解CSP的难度。几个精确的猜想已经被提出，预测了哪些方程会导致这个结果

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, and which has led to major breakthroughs in our understanding of the complexity of CSPs over the past 20 years. In short, every family of constraints is transformed into a mathematical object whose algebraic properties reflect the difficulty of solving the CSP. Several precise conjectures have been formulated, predicting which equations should lead to solvability with given time and space restrictions. The goal of this program is to investigate and solve these conjectures in various important special cases. The investigation of special cases of the refined dichotomy conjectures is bound to provide insights into an eventual solution of the full L- and NL- conjectures. This will give us a complete classification of the complexity of CSPs of bounded width, and hence a much deeper understanding of the complexity of non-uniform CSPs, which are ubiquitous in the theory of computing, with wide-ranging applications from artificial intelligence to database theory.