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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-02 Page: https://delphi.science/r/arxiv/2602.02302 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…