Project Details
Projekt Print View

Homogeneous structures, constraint satisfaction problems, and topological clones

Subject Area Mathematics
Theoretical Computer Science
Term from 2015 to 2019
Project identifier Deutsche Forschungsgemeinschaft (DFG) - Project number 280296726
 
Final Report Year 2020

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

 
 

Additional Information

Textvergrößerung und Kontrastanpassung