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

代数在研究约束满足问题的细粒度计算复杂性中的应用

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

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.

在约束满足问题（CSP）中，必须分配 值转换为必须满足各种约束的变量;典型的 真实的世界的例子包括调度问题，数据库查询， 图像处理和频率分配问题。总的来说， 确定CSP是否承认解决方案是一种算法， 挑战，但在实践中经常发生的是， 是一个非常有限的形式，允许使用有效的 解决CSP的方法。我们的长期目标是 究竟是什么样的限制导致了这些易处理的 CSP的。我们的方法是基于一个意想不到的和富有成效的 CSP和泛代数之间的联系 90年代末，P. Jeavons。总之，每个家庭 约束被转换为数学对象， 代数性质在某种程度上反映了解决这些问题的难度。 CSP。 这种代数方法带来了一些重大突破 在过去的10年里，在对算法复杂性的研究中， 约束满足问题