{"id":"arxiv/2602.02302","url":"https://arxiv.org/abs/2602.02302","tags":["math.LO","cs.LO"],"score":0,"title":"Decidability of Interpretability","domain":"math.LO","source":"arxiv","authors":["Roman Feller","Michael Pinsker"],"reviews":0,"subject":"math.LO","summary":"The Bodirsky-Pinsker conjecture asserts a P vs. NP-complete dichotomy for the computational complexity of Constraint Satisfaction Problems (CSPs) of first-order reducts of finitely bounded homogeneous structures. Prominently, two structures in the scope of the conjecture have log-space equivalent CSPs if they are pp-bi-interpretable, or equivalently, if their polymorphism clones are topologically isomorphic. The latter gives rise to the algebraic approach which regards structures with topologically isomorphic polymorphism clones as equivalent and seeks to identify structural reasons for…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-02","reactions":{}}