Robustly Tractable Constraint Satisfaction Problems

约束满足问题，简称CSP，提供了一个通用的框架，在这个框架中，可以以自然的方式表达人工智能和计算机科学中的各种问题。约束满足问题的基本目标是决定是否有一个值分配给一组给定的变量，受约束的值可以同时分配给某些指定的变量子集（决策版本，CSP），或找到一个分配满足最大数量的约束（优化版本，最大CSP）。如今，CSP被广泛用于理论计算机科学，是一个具有非常丰富的结构的数学对象，为分类方法和算法技术提供了一个很好的实验室。在复杂性理论中受到广泛关注的一类CSP是具有固定约束语言的CSP，即对约束类型进行限制。CSP的多项式时间算法通常只需要区分可满足实例和不可满足实例，即对所有不可满足实例都进行相同的处理。什么时候可以使这样的算法也识别接近失败，即几乎可满足的实例-那些可以去除一小部分约束以使实例可满足的实例？我们称这种类型的易处理性为鲁棒的。我们计划开发一个新的研究计划，调查一个概念的CSP与一个固定的约束语言，结合在一个自然的方式两个非常先进的（技术上和概念上），但到目前为止，实际上不相交，方向在计算理论：研究经典的易处理性和近似性的约束满足问题，通过代数/逻辑和分析方法，分别。

The constraint satisfaction problem, or CSP for short, provides a general framework in which it is possible to express, in a natural way, a wide variety of problems from artificial intelligence and computer science. The basic aim in a constraint satisfaction problem is to decide whether there is an assignment of values to a given set of variables, subject to constraints on the values which can be assigned simultaneously to certain specified subsets of variables (decision version, CSP), or to find an assignment satisfying a maximum number of constraints (optimisation version, Max CSP). Nowadays, the CSP is extensively used in theoretical computer science, being a mathematical object with very rich structure that provides an excellent laboratory both for classification methods and for algorithmic techniques. One particular family of CSPs that receives a great amount of attention in complexity theory are the CSPs with a fixed constraint language, i.e. with a restriction on the types of constraints.A polynomial-time algorithm for a CSP, in general, only needs to tell satisfiable instances from unsatisfiable, i.e. it treats all unsatisfiable instances the same. When can such an algorithm be made to also identify near-misses, i.e. almost satisfiable instances - those where a tiny fraction of constraints can be removed to make the instance satisfiable? We call this type of tractability robust. We plan to develop a new research programme investigating a notion of tractability for CSP with a fixed constraint language that combines in a natural way two very advanced (both technically and conceptually), but so far practically disjoint, directions in the theory of computation: studying classical tractability and approximability of constraint satisfaction problems via algebraic/logical and analytic methods, respectively.