Descriptive Complexity and Constraint Satisfaction Problems

We give a common generalization of two theorems from Descriptive Complexity: the Immerman-Vardi Theorem, which says that over linearly ordered structures, the logic LFP+C captures PTime and the Cai-Fürer-Immerman Theorem, which says that over all finite structures, the logic LFP+C does not capture PTime. Our generalization relies on a connection with Constraint Satisfaction Problems and recent results from CSP theory. The presented results are a consequence of the results presented in the previous talk by Joanna Ochremiak. Both talks are based on a joint paper with Bartek Klin, Sławomir Lasota and Joanna Ochremiak accepted to CSL-LICS 2014.

Authors

• Szymon Toruńczyk

Keywords

No keywords are indexed for this paper.