Oligomorphic clones: tackling CSPs via the infinite

A clone is a set of finitary functions on a set D which is closed under composition and which contains all projections. There are two major sources of clones: the term operations of any algebra on D form a clone called the term clone of the algebra (and in fact, every clone is of this form); the set of all finitary operations which preserve a given relational structure on D form a clone called the polymorphism clone of the structure (certain clones, the topologically closed clones, are of this form). The first source of clones makes them an object of primary interest in universal algebra, since many properties of an algebra, such as its subalgebras and congruences, only depend on its term operations. The latter links them with relational structures, and in particular with certain questions in complexity theory. This project is about the study of clones over a countably infinite set and their applications in complexity theory. While the investigation of all such clones is not very promising since in the general setting, hardly any positive structural results could be expected, research on clones which are sufficiently rich has proven extremely fruitful in recent years. We will be interested in clones which are rich in the sense that they contain a rather large permutation group: a permutation group on a countably infinite set D is called oligomorphic if and only if its componentwise action on any finite power of D has only finitely many orbits. Clones containing an oligomorphic group, referred to as oligomorphic clones, have been shown to enjoy numerous properties of clones on finite sets. For example, they satisfy a topological variant of Birkhoff`s HSP theorem; moreover, they encode the complexity of certain computational problems, so-called constraint satisfaction problems (CSPs), and indeed have proven to be a valuable tool in the study of the complexity of such problems in what is called the algebraic approach to CSPs. Oligomorphic clones encode a much larger class of CSPs than clones over finite sets, and yet many tools from the finite carry over to the oligomorphic setting. A typical example of computational problems that can be modelled in our setting are Graph- SAT problems: the input of a Graph-SAT problem is a finite set of variables, and statements (constraints) about these variables in the language of graphs taken from a fixed finite set S of allowed statements. The question is whether one can assign vertices in a finite graph to the variables so that all constraints are satisfied. Using the methods of this project, one can show that for any fixed set S of statements about graphs, this problem is either in P or NP- complete. While the focus of this project is on universal algebra and finite computational problems, its methods involve a wide range of concepts from various fields of infinite mathematics: such concepts include homogeneous structures from model theory, Ramsey-type theorems from combinatorics, and topological groups.

Constraint Satisfaction Problems (CSPs) are computational problems where one is given variables and constraints about these variables, and the question is whether the variables can be assigned values in such a way that all constraints are satisfied. For example, one might be given an equation using variables, addition and multiplication, and wonder whether it has a solution in the natural numbers. In another problem, one is given a logical expression using variables and the connectives AND, OR, and NOT, and has to decide whether the variables can be assigned truth values TRUE or FALSE in such a way that the whole logical expression becomes TRUE. In a third example, one is given points and some lines connecting some of the points, and the question is whether the points can be split into two classes in such a way that no line connects two points within the same class (here the points are viewed as variables, and the possible values are the two classes). Some CSPs can be solved by a computer; of the examples above, this is the case precisely for the second and the third. When a CSP can be solved by a computer, it might still be so hard that the solution cannot be computed in reasonable time. In this project, we consider "polynomial time in the size of the given instance of the problem" reasonable. The class of "reasonable" problems is called P, and the splitting problem above is an example of a problem in P. In contrast, the mentioned problem concerning logical expressions is believed not to be reasonable (this is unknown, and among of the most famous open questions of mathematics). Computational problems which are at least as hard as this problem are called NP-hard. It has been conjectured that a large class of CSPs exhibit a complexity dichotomy: they are either reasonable (in P), or very unreasonable in the sense that they are NP-hard; that is, there are no CSPs in the class which are outside P, but not NP-hard. This project aimed at verifying this conjecture for certain subclasses, and providing a characterization of those CSPs which are conjectured to be in P. We found that all CSPs which ask about certain properties in partially ordered sets do satisfy the conjectured dichotomy. Moreover, we found that those CSPs which are conjectured to be in P show a certain symmetry which is described by a concrete equation, namely u(s(x,y,x,z,y,z))=v(s(y,x,z,x,z,y)).