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.

The immediate impact of the proposed research is the creation of foundational knowledge concerning the concept of efficient computation, thus contributing to the development of the theory of computation. Our research can be considered as the ``proof of concept'' type of
research because we intend to investigate an effectively new notion of tractability for a wide class of computational problems, providing efficient algorithms for and identifying inherent barriers to a certain type of efficient computation. Our research will also contribute to the development and the synergy of several areas of mathematics (including algebra, logic, discrete mathematics, mathematical programming), as we intend to connect two very advanced areas within theory of computation that have previously used rather different mathematical toolkits. We expect considerable international interest in results of our research from several communities within computer science and mathematics. We consider researchers from these communities to be the immediate beneficiaries of our research.

We plan to study constraint satisfaction problems which play an important role in artificial intelligence, specifically in its subarea called constraint programming (CP). Even though it is not our immediate objective, our findings can potentially be applied in constraint programming, though the development of such applications would certainly require a separate serious effort and deep knowledge of CP.

Algorithms are at the very heart of computing, and the practical applications of algorithms are ubiquitous. Multinational companies such as Google and Microsoft have research groups in algorithms and computational complexity and have close associations with researchers in strong theoretical computer science research groups in universities such as MIT, Harvard and Stanford. It cannot be doubted that the theory of computation, and computational complexity theory in particular, has made, and continues to make, significant impact on technology. It guides practical problem solving by providing a conceptual framework in which to reason about tractability and intractability of computational tasks, thus giving a programmer/algorithm designer valuable advice as to what is a good way to formulate (or possibly relax) the task at hand and what kind of algorithmic solution is most suitable for it. Moreover, concrete results providing improved algorithms or computational hardness (often obtained without having an eventual application in mind) are used in applications. This impact is clearly seen on the example of Internet-based activities which so strongly affect all aspects of our life nowadays. Good algorithms provide fast search (which is the main activity on the Internet), while computational hardness of certain problems guarantees security of cryptographic protocols, hence the huge economic potential of e-commerce on the Internet. It should be noted, however, that practical problems often come bundled together with a lot of messy application-specific detail, and it is important to have a body of algorithmic knowledge about the essential and mathematically clean core of such problems, upon which concrete applications can be built. Our research concerns rather general computational problems, and hence contributes to building this body of knowledge.

Finally, we see our research as helping to promote the subject within the UK and adding to the presence of high quality theoreticians whose research and skills will be of interest to high-tech industries.