Turing machines with atoms, constraint satisfaction problems, and descriptive complexity
Bartek Klin, Sławomir Lasota, Joanna Ochremiak, Szymon Toruńczyk · 2014
We study deterministic computability over sets with atoms. We characterize those alphabets for which Turing machines with atoms determinize. To this end, the determinization problem is expressed as a Constraint Satisfaction Problem, and a characterization is obtained from deep results in CSP theory. As an application to Descriptive Complexity Theory, within a substantial class of relational structures including Cai-Fürer-Immerman graphs, we precisely characterize those subclasses where the logic IFP+C captures order-invariant polynomial time computation.