The Complexity of Promise Constraint Satisfaction

Why is it that some computational problems admit algorithms that always work fast, i.e. scale up well with the size of data to be processed, while other computational problems are not like this and (appear to) admit only algorithms that scale up exponentially? Answering this question is one of the fundamental goals of theoretical computer science. Computational complexity theory formalises the two kinds of problems as tractable and NP-hard, respectively. So we can rephrase the above question as follows: What kind of inherent mathematical structure makes a computational problem tractable? This very general question is known to be extremely difficult. The Constraint Satisfaction Problem (CSP) and its variants are extensively used towards answering this question for two reasons: on the one hand, the CSP framework is very general and includes a wide variety of computational problems, and on the other hand, this framework has very rich mathematical structure providing an excellent laboratory both for complexity classification methods and for algorithmic techniques.

The so-called algebraic approach to the CSP has been very successful in this quest for understanding tractability. The idea of this approach is that non-trivial algebraic structure (which can viewed roughly as multi-dimensional symmerties) in problem instances leads to tractability, while the absence of such structure leads to NP-hardness. This approach has already provided very deep insights and delivered very strong complexity classification results. It is a common perception that the power of this approach comes largely from the fact that symmetries can be composed, i.e. cascaded, to form another symmetry. The proposed researh will challenge this perception and extend the algebraic approach significantly beyond this seemingly indispensable property. Thus, we will provide further very strong evidence to the thesis that tractable problems posess algebraic structure. We will also apply our new theory to resolve long-standing open questions about some classical NP-hard optimisation problems, specifically how much the optimality demand must be relaxed there to guarantee tractability.

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 plan to build a general theory that provides a unified mathematical explanation for (in)tractability within a wide class of computational problems. 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 these communities as the main immediate benefactors of our research.

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, Princeton, 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, hence the huge economic potential of e-commerce on the Internet. It should be noted, however, that practical problems usually 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 are built. Our research concerns rather general computational problems, and hence contributes to building this body of knowledge. General theory, such as the one we propose to build, rarely directly delivers practical efficient algorithms for specific problems, but in hte longer term it can have a much more fundamental transformative effect on the way we think about solving problems.

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.