Applications of algebra and topology to constraint satisfaction problems

代数和拓扑在约束满足问题中的应用

• 批准号: 238899-2006
• 负责人: Larose, Benoît
• 金额: $ 0.8万
• 依托单位: Concordia University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2006
• 资助国家: 加拿大
• 起止时间: 2006-01-01 至 2007-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=339954
• 关键词: Applications; algebra; topology; constraint; satisfaction

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.

在约束满意度问题（CSP）中，必须将值分配给必须遵守各种约束的变量；典型的现实世界示例包括调度问题和数据库查询。通常，确定CSP是否承认解决方案是一种算法挑战，但是在实践中通常会发生约束的形式非常有限，从而允许使用有效的方法来解决CSP。我们的长期目标是精确地对这些可行的CSP进行哪些类型的限制。我们的方法是基于CSP和通用代数之间意外而富有成果的联系，该代数在90年代后期被P. Jeavons发现。简而言之，每个约束家族都被转变为一个数学对象，其代数属性在某种程度上反映了解决CSP的困难。从代数拓扑领域借来的其他方法用于分析这些代数对象。在过去5年中，这种代数方法在研究约束满意度问题的算法复杂性方面导致了一些重大突破。