Decidability of Interpretability
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.02302
curl -X POST /api/v1/records/arxiv/2602.02302/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.02302/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'