Applications of algebraic methods in combinatorial problems

约束满足问题(CSP)提供了一个通用框架，在该框架中可以 以自然的方式表达各种各样的问题，包括许多关键的现实世界问题 调度、路由、数据库等。CSP中的目标是找到分配给 值赋给给定的一组变量，受值的约束，这些值可以同时 赋值给某些指定的变量子集。在计数约束满足问题中 我们的目标是找出这类作业的数量。因此，CSP在 理论上和实践上都有大量的应用。在理论应用中，我们寻找新的 算法思想，可以帮助解决以前无法解决的问题，以改进 现有的算法，以设计更通用和统一的算法，并找到证据，确定 在一般情况下，问题是不能有效解决的。在实际应用中，约束和 可满足性求解器现在是从调度到硬件的广泛领域的标准工具 核实。CSP研究的进展将加快这种求解器的速度，并扩大它们的领域 适用性。 本项目侧重于CSP研究的理论方面。它的主要目标之一是准确地 了解哪些CSP和计数CSP可以有效解决，并设计有效的解决方案 算法。最近在理解CSP的困难方面取得了重大进展， 自然而然的下一步是将实现这一突破的方法扩展到更广泛的范围 一连串的问题。CSP研究中最有效的工具之一就是抽象的方法 代数。我们计划开发这些方法，以便在其他领域发挥作用。其中一个领域是近似地 在计时。这一领域与统计物理学有着惊人的联系，在统计物理学中，这样的数字影响着 大颗粒系综的性质，特别是有助于定位相变阈值， 例如，在这个过程中，液体变成了气体。当CSP和计数CSP被很好地建立时 除了研究领域，我们还计划冒险进入非常新的领域。CSP的进一步推广， Promise CSP是最近提出的，其中，给定两个CSP实例，更具限制性的 一个，一个更宽松的，我们被承诺限制实例有一个解决方案，并询问 找到松弛实例的解。这个问题的表现力比 常规CSP。对Promise CSP的代数方法的某些元素已经被开发出来 最近，一个针对Promise CSP分类的项目非常活跃。

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.