Homogeneous structures, constraint satisfaction problems, and topological clones
Theoretical Computer Science
Final Report Abstract
The DFG-funded project Topo-Klon investigated topological clones and their use when classifying the computational complexity of constraint satisfaction problems (CSPs). CSPs are computational problems that arise in many areas of theoretical computer science, such as temporal and spatial reasoning in artificial intelligence or optimisation. In such a problem, we are given a finite number of variables and a finite number of constraints, and the task is to decide whether there exists a solution that satisfies all the given constraints. Many CSPs can be modelled by fixing a (finite or infinite) structure, whose values represent the possible values for the variables of the constraint satisfaction problem. One of the central questions about these problems is when (depending on the fixed structure) they can be solved efficiently (e.g., in polynomial time on a classical computer), and when they are computationally difficult. A classical approach in mathematics is to study structures via their symmetries, often captured by the automorphism group of the structure. However, the automorphism group in general does not capture enough information about the structure to predict the complexity of the respective CSP. Polymorphisms, a higher-dimensional generalisation of the notion of an automorphism, do capture the complexity of the CSP for finite structures, and even for a large class of countably infinite structures, known as ω-categorical structures in model theory. The set of all polymorphisms forms a clone, which is a central concept from universal algebra. Similarly as it is advantageous to study automorphism groups as topological groups, polymorphism clones are considered as topological clones with respect to a natural topology. Moreover, the complexity of the CSP is in fact fully determined by this topological clone. The theory of topological clones turned out to be a very fruitful concept, drawing some of its inspiration from the well-developed theory of topological groups. The project contributed to its development in several directions; one of the results being a way how to apply deep universal-algebraic results about finite algebras to study topological clones. The many application areas from theoretical computer science abundantly provide examples and the systematic study of the computational complexity of CSPs led to many new fascinating questions about topological clones.
Publications
- A topological characterisation of endomorphism monoids of countable structures. Algebra Universalis, 77(3):251-269, 2017
Manuel Bodirsky and Friedrich Martin Schneider
(See online at https://doi.org/10.1007/s00012-017-0427-2) - ACM Transactions on Computational Logic (TOCL), 18(3), 2017
Manuel Bodirsky, Peter Jonsson, and Trung Phan Pham
- Transactions of the AMS, 369(5):3707- 3740, 2017
Manuel Bodirsky, Michael Pinsker, and András Pongrácz
(See online at https://doi.org/10.1090/tran/6937) - A Dichotomy for First-order Reducts of Unary Structures. Logical Methods in Computer Science 14(2), 2018
Manuel Bodirsky, Antoine Mottet
(See online at https://doi.org/10.23638/LMCS-14(2:13)2018) - A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP. Proceedings of LICS 2018
Manuel Bodirsky, Florent Madelaine, and Antoine Mottet
- Discrete Temporal Constraint Satisfaction Problems. Journal of the ACM 65(2): 9:1-9:41, 2018
Manuel Bodirsky, Barnaby Martin, and Antoine Mottet
(See online at https://doi.org/10.1145/3154832) - Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. Siam Journal on Computing, 49(4): 1224-1264, 2019
Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz
(See online at https://doi.org/10.1137/16M1082974)
