Meta-Questions in Infinite-Domain Constraint Satisfaction

In theoretical computer science, Constraint Satisfaction Problems (CSPs) provide an abstraction of the satisfiability problem for systems of equations. Given a finite set of variables and a finite set of constraints over these variables, the task is to find an assignment of values from some fixed domain for the variables so that all constraints are satisfied simultaneously. For example, the constraints could be linear equations with rational coefficients and the domain the set of all rational numbers; the task is then to decide their solvability in the usual sense. We say that a CSP is finite-domain if the associated variable domain is finite and infinite-domain otherwise. One of the central topics in the study of CSPs is understanding which problems can be solved efficiently and which problems are computationally hard. Coming back to our example, systems of linear equations can be solved efficiently over the rational numbers, using the Gaussian elimination method, but not over the natural numbers. There, the existence of an efficient algorithm would imply efficient solvability for many other difficult tasks, and in particular resolve the P=NP millennium problem. To systematically study the computational complexity of CSPs, one had to go way beyond the framework in which such problems were originally formulated. The first step was to understand that the algebraic structure underlying these problems needs to be considered to classify their computational complexity; this fundamental insight was enough to classify all two-element domain CSPs. A complexity classification for all finite-domain CSPs was obtained almost half a century later by an intricate combination of deep results from the structure theory of finite algebras. The classification shows that every finite-domain CSP is either efficiently solvable or already as hard as the hardest problem within the class of all finite-domain CSPs. The degree of generality the CSP framework provides over infinite domains is immense; for this reason, infinite-domain CSPs are typically only studied under additional structural restrictions. There is an active research program focused on extending the algebraic approach to CSPs over infinite-domains, together with a conjecture extending the finite-domain CSP dichotomy theorem. However, the precise connection between the algebraic structure underlying infinite-domain CSPs and their algorithmic properties remains poorly understood. The aims of the project are to better understand how the infinite-domain CSP conjecture behaves from the algorithmic perspective, whether it can be simplified, and to what degree is it interesting for other subfields of theoretical computer science. The methods will be diverse, e.g., comparative studies with previously obtained results at the intersection of the field with database theory, structural Ramsey theory, and topological dynamics, as well as an analysis of several meta-questions surrounding the conjecture.

No additional funding sources recorded.