Topological Clones and the Computational Complexity of Constraint Satisfaction Problems
Topological Clones and the Computational Complexity of Constraint Satisfaction Problems
Talk by Manuel Bodirsky
- Location: WIL B 321
- Start: 13. May 2015 at 5:00 pm
- End: 13. May 2015 at 6:30 pm
- Research group: Knowledge-Based Systems
- iCal
Constraint Satisfaction Problems (CSPs) are fundamental computational problems that appear in many areas of theoretical computer science. We are given a finite set of variables and constraints, and would like to know whether there exists an assignment of values to the variables that satisfies all the constraints. For example Boolean satisfiability problems, graph k-colorability, and the feasibility problem for linear programs can be cast as CSPs. It is a major research theme to classify the CSPs that can be solved in polynomial time, and those that are computationally difficult (NP-hard).
When the variables can only take values from some fixed finite domain, it has been conjectured by Feder and Vardi that, depending on the allowed constraints in the input, the CSP is either in P or NP-hard. The most successful and fruitful approach to this conjecture is based on concepts and results from universal algebra.
I will give an introduction to the universal-algebraic approach for the more general situation when the underlying domain is infinite. It turns out that for a large class of CSPs, the computational complexity only depends on the topological polymorphism clone of the allowed constraints. The study of these topological clones (which can be viewed as a multi-variate generalisation of topological automorphism groups) leads to many questions of independent interest in universal algebra and model theory, but also in Ramsey theory and topological dynamics.
