First-order definable Constraint Satisfaction Problems

First-order definable structures with atoms are infinite, but exhibit enough symmetry to be effectively manipulated. We study Constraint Satisfaction Problems (CSPs) where both the instance and the template can be definable structures with atoms. We argue that such templates and instances occur naturally in Descriptive Complexity Theory. In this talk we will concentrate on CSPs over finite templates and infinite, definable instances. In this case even decidability is not obvious, and to prove it we apply results from topological dynamics. We also prove that the complexity of solving such CSPs is one exponential level higher than the complexity of the finite CSP problem over the same template.

Authors

• Eryk Kopczyński

Keywords

No keywords are indexed for this paper.