Robustly Tractable Constraint Satisfaction Problems

点击翻译按钮获取中文摘要

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.