Constraint Satisfaction Problems: beyond the finite case

In a Constraint Satisfaction Problem, one is given a finite set of variables as well as a finite set of constraints on the variables; the question is whether there is a solution to the given constraints, that is, whether the variables can be assigned value s in such a way that all the imposed constraints are satisfied. In this project, we exclusively focus on so -called fixed- template Constraint Satisfaction Problems where the values which the variables can take, as well as the kind of constraints which can be imposed on them, are fixed beforehand. An example is the problem where one is given variables and a system of linear equations with rational coefficients in which these variables appear; these equations are the constraints imposed on the variables. Whether or not such a system of linear equations has a solution in the rational numbers can be decided by applying the Gaussian algorithm. Another example is the problem where one is given a generalised Sudoku, i.e., a square of size (n2)x(n2) for some natural number n, in which some fields are prefilled with natural numbers; the question is whether the empty fields can be completed with natural numbers in such a way that the rules of Sudoku are respected. Here, the variables are simply the empty fields, the constraints are given by the rules of Sudoku, and the allowed values for the variables are the natural numbers. A third example is the problem where one is given variables, and some constraints which demand that some variables be strictly smaller than some other variables; the question is whether the variables can be assigned natural numbers in such a way that all constraints are satisfied. As one can easily see, this question has a positive answer if and only if the constraints do not imply that one variable is strictly smaller than itself. The rough goal of this project is to distinguish those Constraints Satisfaction Problems which can be solved efficiently by an algorithm from those which cannot; here, efficient is synonymous with in polynomial time, which means in a number of steps which is bounded by a fixed polynomial applied to the number of given variables. Of the three examples above, only the first and the third can be solved efficiently, unless the famous P=NP millennium problem has a positive answer. If the set of allowed values for the variables is finite, e.g., if the variables are to take one of the truth values 0 or 1, then we have a perfect understanding which Constraint Satisfaction Problems can be solved efficiently: they can be characterised by clear structural conditions on the kind of constraints allowed. This project aims at achieving a similar understanding for certain Constraint Satisfaction Problems where the variables take values in an infinite set.