Algebraic Theory for Promise Constraint Satisfaction Problem

Intuitively, the computational complexity of a computational problem is a measure of the difficulty of the problem. Computers, undoubtedly, play a large role in our everyday lives, and so understanding which computational tasks are feasible is of a high priority, with countless applications, for example in artificial intelligence. The aim of this project is to study the computational complexity of a class of problems known as Promise Constraint Satisfaction Problems, or PCSPs for short. This class generalises Constraint Satisfaction Problems, or CSPs, another important and well-studied class of problems. Informally, an instance of a CSP or PCSP is a problem akin to a sudoku, that is the problem of assigning values to an input set of variables under some constraints. Unlike the usual sudoku, however, we only want to know if such an assignment exists, rather than to explicitly find one. The difference between CSPs and PCSPs is that in the latter case we have two sets of possible values, one of which is more restrictive, and we want to decide between the existence of such an assignment with values from the first set, or the non-existence from the second. Recently, a major breakthrough has been achieved in the study of CSPs. The computational complexity of the CSPs has been classified in the case when there are only finitely many possible values to assign to the variables. The essential observation for this classification is the fact that the complexity of a CSP only depends on a certain algebraic object associated with it, called polymorphism clone. As a consequence, a fruitful algebraic theory has been developed which eventually led to the proof of the classification mentioned above. The methods from CSPs do not apply to PCSPs directly, however, it is already known that the computational complexity of a PCSP is encoded in a different algebraic object, called polymorphism clonoid. In this project, we develop the algebraic theory for polymorphism clonoids, inspired by the one developed for polymorphism clones. Unlike in the other research on clonoids, this project has a strong emphasis on the algebraic theory for clonoids which correspond to certain infinite PCSPs, that is the case when there are infinitely many values to assign to the variables. This broader setting brings together methods from other branches of mathematics such as Mathematical Logic, Topology, and Combinatorics, which are not necessary in the finite case. Progress on this project will enhance the understanding of the fundamentals of computation.

Computational complexity of a (computational) problem can be thought to be a measure of how easy or difficult it is to solve the said problem. In practice, we want to know how much time or other computer resources such a computation is expected to require and how this amount changes when input sizes are scaled up. For example, if an internet search engine needs to process 10 times more websites then before, are the resources necessary for this 10 times higher, 100 times higher, or is the growth exponential. The answer to this question can have profound implications on what is feasible to compute. The aim of this project was to study the computational complexity of a certain important class of problems known as Promise Constraint Satisfaction Problems, or PCSP for short. PCSP is a proper generalisation of another well studied class of problems - Constraint Satisfaction Problems, or CSP. In the last few years, a major breakthrough has been achieved in the study of CSP, that is the computational complexity of the CSP over a large and natural class has been classified. The essential observation for this classification was the fact that the computational complexity of a CSP only depends on a certain algebraic object associated with it, called polymorphism clone. As a consequence, a fruitful algebraic theory has been developed which eventually led to the proof of the classification mentioned above. It had already been established that in the case of PCSP there also exists an associated algebraic object, called polymorphism clonoid, which encodes the computational complexity. Of particular interest in this project was the case when the underlying structures which define a particular Promise Constraint Satisfaction Problem are infinite but well-behaved. In such cases beside the algebraic structure one can make use of an additional topological structure, which have proven useful in the realm of CSP. The main research outcomes of the project underline the importance of topology and its interactions with the algebraic structure. On one hand, we demonstrate that for certain well-studied structures there is a unique topology which is compatible with the algebraic structure of the polymorphism clone. On the other hand, we show that a recent results about the relevance of topology (in a dichotomy conjecture for infinite-domain constraint satisfaction problems) also apply for CSP templates, that is, structures which give rise to CSP in a sensible way.