The complexity of the constraint satisfaction problem and its variants

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

• 批准号: RGPIN-2015-04656
• 负责人: Bulatov, Andrei
• 金额: $ 3.13万
• 依托单位: Simon Fraser 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=589932
• 关键词: 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.

约束满足问题(CSP)提供了一个通用的框架，在该框架中可以以自然的方式表达各种各样的问题。CSP的目标是找出给定变量集的赋值，约束条件是可以同时赋值给特定变量子集的值；在计数约束满足问题中，目标是找出这种赋值的数目。因此，CSP在许多应用中都非常重要，无论是在理论上还是在实践中。在理论应用中，我们寻找新的算法思想，帮助解决以前无法解决的问题，改进现有的算法，设计更通用和统一的算法，并找到某些问题在一般情况下不能有效求解的证据。在实际应用中，约束和可满足性求解器现在是从调度到硬件验证等广泛领域的标准工具。CSP研究的进展将加快这种求解器的速度，扩大其适用范围。