Constraint Network Tractability: Beyond Structure and Language

约束满足问题（英语：Constraint Satisfaction Problem，缩写为CSP）是一个通用的计算问题框架，它涉及到寻找一组值，这些值一起满足一些特定的约束，称为约束。这样的问题在非常广泛的应用中遇到，包括运筹学和人工智能中的经典问题，许多形式的调度和规划问题，以及密码学，计算机视觉，化学合成和基因匹配中的问题。最大约束满足问题（Max-CSP）是CSP的一个推广，它的应用范围甚至更大：它包括许多在基本CSP框架中不容易表达的组合优化问题。在这个问题中，我们的目标是找到一个分配给问题变量的值，使满足的约束数最大化。CSP和Max-CSP都是NP-困难的，这意味着不太可能存在有效的通用算法来解决所有的问题。因此，人们可以尝试设计在某些情况下表现良好的算法，或者可以限制一般问题以获得更易处理的问题（例如，可以在多项式时间内解决的问题）。我们的研究主要集中在第二种方法上：我们试图识别约束满足问题的约束条件，这些约束条件足以确保问题能够有效地解决。在这个项目中，我们的目标是找到一种新的方法来定义这样的约束条件，这种方法比以前考虑过的任何方法都更强大，并且允许我们识别更多种类的易处理问题。在过去，被认为是唯一的易处理的问题分为两个不同的类。在第一种情况下，约束是任意的，但它们只能以有限的方式应用于变量。在第二种情况下，约束属于约束类型的受限家族，但它们可以以任意方式应用于变量。这两种限制都导致了有趣的数学理论，以及一些可以有效解决的重要特例。然而，我们相信，现在有可能将这些方法联合收割机并获得一个更普遍的理论，该理论统一了以前的方法，并提供了一种更灵活的方法来定义问题的限制。通过开发这种更强大的方法，我们希望能够更准确地描述哪种约束问题可以有效地解决，并利用这些信息改进现有的软件工具和分析技术。

The Constraint Satisfaction Problem (or CSP) is a general framework for all kinds of computational problems that involve searching for a set of values that together satisfy some specified restrictions, known as constraints. Such problems are encountered in a very large range of applications, including classic problems in operations research and artificial intelligence, many forms of scheduling and planning problems, and problems in cryptography, computer vision, chemical synthesis and gene matching. The Maximum Constraint Satisfaction Problem (or Max-CSP) is a generalisation of the CSP whose range of application is even greater: it includes many combinatorial optimisation problems that are not easily expressed in the basic CSP framework. In this problem the aim is to find an assignment of values to the variables of the problem which maximises the number of satisfied constraints.Both the CSP and the Max-CSP are NP-hard, which means that it is unlikely that there exist efficient general algorithms that can solve all instances of such problems. Thus one can try to design heuristics which perform well on certain kinds of instances, or else one can restrict the general problem in order to obtain a more tractable problem (for example, a problem which can be solved in polynomial time). Most of our research is concerned with the second approach: we try to identify the restrictions on constraint satisfaction problems which are sufficient to ensure they can be solved efficiently.In this project we aim to find a novel approach to defining such restrictions that is more powerful than anything that has been considered before, and allows us to identify many more kinds of tractable problems. In the past, the only kinds of tractable problems that have been considered fall into two distinct classes. In the first, the constraints are arbitrary, but they can only be applied to the variables in limited ways. In the second, the constraints fall into a restricted family of constraint types, but they can be applied to the variables in an arbitrary way. Both of these kinds of restrictions have led to interesting mathematical theories, and some important special cases which can be solved efficiently. However, we believe that it is now possible to combine these approaches and obtain a much more general theory that unifies the previous approaches, and provides a more flexible way to define the restrictions on problems.By developing this more powerful approach we hope to be able to describe much more accurately which kinds of constraint problems can be solved efficiently, and to use this information to improve the available software tools and analytical techniques.