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

点击翻译按钮获取中文摘要

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.