Showing math.LOShow all
2 papers · 1 filter
math.LO2026
Decidability of Interpretability
Roman Feller, Michael Pinsker
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…
math.LO2025
The random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra
Michael Pinsker, Jakub Rydval, Moritz Schöbi +1
We prove that the random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra, hereby answering an open question of Bartošová and Scow.