Applications of algebraic methods in combinatorial problems

代数方法在组合问题中的应用

• 批准号: RGPIN-2020-05481
• 负责人: Bulatov, Andrei
• 金额: $ 4.66万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=740614
• 关键词: Applications; algebraic; methods; combinatorial; problems

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 including many crucial real-world problems in scheduling, routing, databases, etc. 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 focuses on the theoretical side of the CSP research. One of its main goals is to precisely understand which CSPs and counting CSPs can be solved efficiently and design efficient solution algorithms. Major progress has been made very recently in understanding the hardness of the CSP, and a natural next step is to extend the methods used to achieve this breakthrough to a wider range of problems. One of the most efficient tools in the study of the CSP applies methods of abstract algebra. We plan to develop these methods to work in other areas. One of such areas is approximate counting. This area has surprising connections to statistical physics, where such numbers affect the properties of large ensembles of particles, and, in particular, help to locate phase transition thresholds, at which, for instance, liquid turns to gas. While the CSP and the counting CSP are well established research areas, we also plan to venture into very new territory. A further generalization of the CSP, the Promise CSP, has been recently proposed, in which, given two CSP instances, a more restrictive one, and a more relaxed one, we are promised that the restrictive instance has a solution and asked to find a solution of the relaxed instance. This problem has much greater expressive power than the regular CSP. Certain elements of the algebraic approach to the Promise CSP have been developed recently, and a project aiming at a classification of Promise CSPs is very active.

约束满足问题（CSP）提供了一个通用框架，在这个框架中，可以用一种自然的方式表达各种各样的问题，包括调度、路由、数据库等方面的许多关键的现实问题。CSP的目标是找到一组给定变量的赋值，这些值受到可以同时赋值给某些指定变量子集的值的约束。在计数约束满足问题中，目标是找出这样的分配的数量。因此，CSP在许多理论和实际应用中都非常重要。在理论应用中，我们寻找新的算法思想，可以帮助解决以前无法解决的问题，改进现有的算法，设计更通用和统一的算法，并找到某些问题在一般情况下无法有效解决的证据。在实际应用中，约束和可满足性求解器现在是从调度到硬件验证的广泛领域的标准工具。CSP研究的进展将加快这类求解器的速度并扩大其适用范围。本项目侧重于光热发电理论方面的研究。其主要目标之一是精确地了解哪些csp和计数csp可以有效地求解，并设计有效的求解算法。最近在理解CSP硬度方面取得了重大进展，下一步自然是将用于实现这一突破的方法扩展到更广泛的问题。抽象代数的方法是研究CSP最有效的工具之一。我们计划将这些方法推广到其他领域。其中一个领域是近似计数。这一领域与统计物理学有着惊人的联系，这些数字影响着大粒子群的性质，特别是，有助于定位相变阈值，例如，在这个阈值上，液体变成气体。虽然CSP和计数CSP是成熟的研究领域，但我们也计划冒险进入非常新的领域。最近提出了对CSP的进一步推广，即承诺CSP，其中给定两个CSP实例，一个是更严格的限制实例，一个是更宽松的限制实例，我们被承诺限制实例有一个解，并要求找到放松实例的解。这个问题比常规的CSP具有更强的表现力。最近开发了Promise CSP的代数方法的某些要素，并且一个旨在对Promise CSP进行分类的项目非常活跃。