Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
This provides a foundational complexity classification for infinite-domain CSPs, advancing the open Bodirsky-Pinsker conjecture, which is significant for theoretical computer science and logic.
The paper tackles the complexity of constraint satisfaction problems (CSPs) over infinite structures, proving that for first-order expansions of finitely bounded homogeneous model-complete cores, CSPs are either first-order definable (in non-uniform AC^0) or L-hard under first-order reduction, establishing a general dichotomy within the Bodirsky-Pinsker conjecture.
Feder-Vardi conjecture, which proposed that every finite-domain Constraint Satisfaction Problem (CSP) is either in P or it is NP-complete, has been solved independently by Bulatov and Zhuk almost ten years ago. Bodirsky-Pinsker conjecture which states a similar dichotomy for countably infinite first-order reducts of finitely bounded homogeneous structures is wide open. In this paper, we prove that CSPs over first-order expansions of finitely bounded homogeneous model-complete cores are either first-order definable (and hence in non-uniform AC$^0$) or L-hard under first-order reduction. It is arguably the most general complexity dichotomy when it comes to the scope of structures within Bodirsky-Pinsker conjecture. Our strategy is that we first give a new proof of Larose-Tesson theorem, which provides a similar dichotomy over finite structures, and then generalize that new proof to infinite structures.