Applications of algebra and topology to constraint satisfaction problems

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

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.