The complexity of the constraint satisfaction problem and its variants

约束满足问题及其变体的复杂性

• 批准号: RGPIN-2015-04656
• 负责人: Bulatov, Andrei
• 金额: $ 3.13万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2018
• 资助国家: 加拿大
• 起止时间: 2018-01-01 至 2019-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=646508
• 关键词: complexity; constraint; satisfaction; problem; its

The constraint satisfaction problem (CSP) provides a general framework in which it is possible to express, in a natural way, a wide variety of problems. The aim in a CSP is to find an assignment of values to a given set of variables, subject to constraints on the values which can be simultaneously assigned to certain specified subsets of variables; in the counting constraint satisfaction problem the objective is to find the number of such assignments. The CSP is therefore very important in a number of applications, both theoretical and practical. In theoretical applications we look for new algorithmic ideas that can help to solve problems that could not be solved before, to improve the existing algorithms, to design more general and uniform algorithms, and to find evidence that certain problems are not efficiently solvable in the general case. In practical applications, constraint and satisfiability solvers are now standard tools in a wide range of areas from scheduling to hardware verification. Advances in the study of the CSP will speed up such solvers and expand their area of applicability.*** This project will contribute in both aspects of constraint problems, although its main focus is on the theoretical side. One of its main goals is to precisely understand which CSPs can be solved efficiently and design an efficient solution algorithm. This is one of the long standing open problems in computer science, but there is evidence that we may be approaching its resolution. Another component of the project is the study of counting constraint satisfaction problems. This area has unlikely connections to statistical physics, where such numbers affect the properties of large ensembles of particle, and, in particular,  help to locate phase transition thresholds, at which, for instance, liquid turns to gas. Finally, this project proposes to study the efficiency and to design new algorithms in the framework that is closer to practical circumstances than the standard worst case approach. It is known that practical problems tend to have a certain property called the power law distribution, and we plan to mathematically study the behaviour of various algorithms on instance of the CSP satisfying this property.**

约束满足问题（CSP）提供了一个通用框架，可以在其中以自然的方式表达各种问题。 CSP 的目标是找到给定变量集的值分配，并受到可以同时分配给某些指定变量子集的值的约束；在计数约束满足问题中，目标是找到此类分配的数量。因此，CSP 在许多应用中都非常重要，无论是理论还是实践。在理论应用中，我们寻找新的算法思想，帮助解决以前无法解决的问题，改进现有算法，设计更通用和统一的算法，并找到某些问题在一般情况下无法有效解决的证据。在实际应用中，约束和可满足性求解器现已成为从调度到硬件验证等广泛领域的标准工具。 CSP 研究的进展将加快此类求解器的速度并扩大其适用范围。*** 该项目将对约束问题的两个方面做出贡献，尽管其主要重点是理论方面。其主要目标之一是精确了解哪些 CSP 可以有效求解并设计高效的求解算法。这是计算机科学中长期存在的悬而未决的问题之一，但有证据表明我们可能正在接近解决它。该项目的另一个组成部分是研究约束满足问题的计数。这个领域与统计物理学不太可能有联系，在统计物理学中，这些数字会影响大型粒子群的特性，特别是有助于确定相变阈值，例如在该阈值下，液体会变成气体。最后，该项目建议研究效率并在比标准最坏情况方法更接近实际情况的框架中设计新算法。众所周知，实际问题往往具有某种称为幂律分布的属性，我们计划在满足该属性的 CSP 实例上对各种算法的行为进行数学研究。 **