Open Collections

Description

Recent work by Nies and Paolini shows that, within the class of automorphism groups of 𝜔-categorical structures without algebraicity, the equivalence relation of topological isomorphism is smooth. Loosely speaking, this means that the equivalence relation is as simple as possible from the perspective of descriptive set theory. This result remains true if, in the statement, one replaces the automorphism group with the endomorphism monoid or the polymorphism clone. In this context, two structures have isomorphic endomorphism monoids precisely when they are bi-interpretable by means of existential positive (e.p.) formulas, so we may think of these equivalence relations interchangeably. In recent work with Feller, we investigate whether tractability on the descriptive set theory side (i.e., smoothness) translates to tractability on the computational complexity side (i.e., decidability). More precisely, we study in what capacity one can decide whether two first-order reducts of possibly distinct 𝜔-categorical homogeneous Ramsey structures are e.p. bi-interpretable. Our findings extend previous results on decidability of definability due to Bodirsky, Pinsker, and Tsankov.