Refined complexity of constraint satisfaction problems

约束满足问题的精细化复杂性

• 批准号: RGPIN-2017-05107
• 负责人: Larose, Benoit
• 金额: $ 1.46万
• 依托单位: Université du Québec à Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2020
• 资助国家: 加拿大
• 起止时间: 2020-01-01 至 2021-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=709953
• 关键词: Refined; complexity; 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, 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.

在约束满意度问题（CSP）中，必须将值分配给必须满足各种约束的变量；典型的现实世界示例包括调度问题，数据库查询，图像处理和频率分配问题。通常，确定CSP是否承认解决方案是一种算法挑战，但是在实践中通常会发生约束的形式非常有限，从而允许使用有效的方法来解决CSP。我们的长期目标是精确地对这些可行的CSP进行哪些类型的限制。我们的方法是基于90年代后期发现的CSP和通用代数之间意外而富有成果的联系，这在过去20年中对CSP的复杂性的理解带来了重大突破。 简而言之，每个约束家族都转化为一个数学对象，该对象的代数特性反映了解决CSP的困难。已经制定了几种精确的猜想，预测哪些方程应领导 通过给定的时间和空间限制来解决。该计划的目的是在各种重要的特殊情况下调查和解决这些猜想。对精制二分法猜想的特殊情况的调查必定会提供有关最终溶液和NL猜想的最终解决方案的见解。这将使我们对有限宽度的CSP的复杂性进行完整的分类，从而更深入地了解非均匀的CSP的复杂性，而CSP的复杂性在计算理论中无处不在，并具有从人工智能到数据库理论的广泛应用。