Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard

Leonid Dorochko, Michał Wrona · 2026

Read Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard by Leonid Dorochko, Michał Wrona (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22691.txt.

Introduction

Leonid Dorochko and Michał Wrona study where a famed split in problem hardness holds for infinite structures. Constraint satisfaction asks if a set of rules can all be met. Their 2026 preprint notes that the finite case was settled: each problem is easy or NP-complete, with no middle.

The Bodirsky-Pinsker conjecture claims the same split for a class of infinite structures. The team probe the border between what first-order logic can state and a wider logic. The work is deep theory of computation. Each border case trims the conjecture's unknowns. The split, if true, is a grand pattern.

Catalog record

CREATORLeonid Dorochko, Michał Wrona
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE102 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-22691

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard Thanks: Funded by the National Science Centre, Poland under the Weave-UNISONO call in the Weave programme, project no. 2021/03/Y/ST6/00171 Affiliation: Faculty of Mathematics and Computer Science, Jagiellonian University, Poland Leonid Dorochko, Michał Wrona Abstract 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. \declaretheorem [name=Claim]claim \declaretheorem [name=Observation]observation \declaretheorem [name=Research Question]rquestion \declaretheorem [name=Theorem,numberwithin=section]theorem \declaretheorem [name=Conjecture,numberwithin=section,sibling=theorem]conjecture \declaretheorem [name=Example,numberwithin=section,sibling=theorem]example \declaretheorem [name=Definition,numberwithin=section,sibling=theorem]definition \declaretheorem [name=Lemma,numberwithin=section,sibling=theorem]lemma \declaretheorem [name=Proposition,numberwithin=section,sibling=theorem]proposition Keywords: constraint satisfaction problems, finitely bounded homogeneous structure, infinite structures, first-order definability, L-hardness, computational complexity, dichotomies 1 Introduction The goal of the computational complexity is to describe the amount of certain resources such as time and space required to solve a computational problem under consideration. Instead of working on a single problem, it is reasonable to work on the whole family of problems admitting a uniform formulation. A general formalism which allows the formulation of many natural computation problems is the Constraint Satisfaction Problem \csp(\mathbb{A}) parametrized by a relational structure \mathbb{A} . Every \mathbb{A} contributes to a different computational problem, e.g., a Boolean satisfiability problem, graph coloring or solving equations over a finite field. An instance of \csp(\mathbb{A}) is a set of constraints built out of variables and relations in \mathbb{A} . The goal is to satisfy all constraints simultaneously by the same assignment to variables. Feder-Vardi conjecture [ 22 ] settled in 2017 independently by Bulatov [ 16 ] and Zhuk [ 38 , 39 ] states that whenever \mathbb{A} is finite, then \csp(\mathbb{A}) is either in P or it is NP-complete. That result stands in the opposition to Ladner’s theorem [ 26 ] on the existence of NP-intermediate problems on the condition that P \subsetneq NP. Although obtaining the dichotomy was the original motivation, the algorithms for all polynomial-time \csp(\mathbb{A}) are arguably of not less importance. They generalize Gaussian elimination [ 25 ] and local-consistency techniques [ 4 ] ubiquitous in constraint solving. Thus, they provide the same way of solving many natural problems in P. On the other hand a simple algebraic condition provides a polynomial time gadget reduction from monotone 1-in-3-SAT to any NP-complete \csp(\mathbb{A}) [ 17 ] . Thereby, the dichotomy proofs provide a deep insight into the nature of the class NP. Although the holy grail of the CSP community has been achieved, it is not the end of the story. Indeed, there is a number of active research directions generalizing \csp(\mathbb{A}) over finite structures \mathbb{A} . In particular, Bodirsky-Pinsker conjecture [ 11 ] extends Feder-Vardi conjecture to some well-behaved infinite structures \mathbb{A} which cover a number of problems not expressible as \csp(\mathbb{A}) if \mathbb{A} is finite, e.g., in temporal and spatial reasoning [ 7 , 30 ] , phylogenetic reconstruction [ 6 , 19 ] and graph theory [ 12 , 9 ] . The well-behaved structures \mathbb{A} are described in two steps. We start with a Fraïssé class [ 24 ] of finite structures \mathcal{C} given by a finite number of finite structures (obstructions) which are forbidden to embed into the members of \mathcal{C} . The Fraïssé limit of \mathcal{C} is the basic structure \mathbb{B} . By Fraïssé theorem the structure \mathbb{B} is homogeneous 1 1 1 All notions are carefully defined in Section 2 . and by the choice of \mathcal{C} it is finitely bounded. Then, one considers and asks about the complexity of \csp(\mathbb{A}) for structures \mathbb{A} first-order definable in \mathbb{B} known as first-order reducts of \mathbb{B} . {conjecture} (Bodirsky-Pinsker) For every finite-signature first-order reduct \mathbb{A} of a finitely bounded homogeneous structure \mathbb{B} , \csp(\mathbb{A}) is in P or it is NP-complete. Although not resolved in full generality, the conjecture has been confirmed in the number of particular cases such as all first-order reducts of (\mathbb{Q},<) , known also as temporal (constraint) languages [ 7 ] , first-order reducts of the so-called rooted triple relation, known also as phylogeny languages [ 6 ] , or all first-order reducts of all homogeneous graphs [ 12 , 9 ] . Another notable classification considers CSPs within the conjecture expressible in the logic MMSNP [ 8 ] . Furthermore, it is worth mentioning that [ 32 ] offers some new algebraic tools which simplify providing similar partial classifications. However, despite all these attempts, it is fair to say that the general conjecture is wide open. At the same time, the boundary between P and NP-complete has not been the only one studied for finite-domain CSPs [ 15 ] . In [ 28 ] one can find a number of not yet resolved conjectures on which CSPs are, e.g., in L (logarithmic space) or NL (non-deterministic logarithmic space). The questions have not been yet answered despite certain partial results available in the literature, see e.g. [ 3 , 21 , 20 , 18 ] . Furthermore, [ 28 ] contains the following dichotomy built on the characterization of first-order definable finite-domain CSPs from [ 27 ] . {theorem} [] (Larose-Tesson) Let \mathbb{A} be a finite structure over a finite signature. Then one of the following holds. • \csp(\mathbb{A}) is L-hard (under first-order reduction). • \csp(\mathbb{A}) is first-order definable, and in non-uniform \text{AC}^{0} . Recall that non-uniform \text{AC}^{0} is the complexity class consisting of all languages accepted by polynomial-size constant-depth families of Boolean circuits and that every first-order definable decision problem is in that class (see, e.g. Theorem 6.4 in [ 29 ] ). Moreover, there are problems in L which are not in non-uniform \text{AC}^{0} [ 23 ] , i.e., \text{non-uniform AC}^{0}\subsetneq L . In particular, any problem which is L-hard under first-order reduction cannot lie in non-uniform \text{AC}^{0} . Since the question on the P versus NP-complete dichotomy for first-order reducts of finitely-bounded homogeneous structures is notoriously resistant and the conjectures from [ 28 ] on CSPs in L and NL are not even solved for finite structures, it is reasonable to ask if at least Theorem 1 may be generalized. In this paper we achieve this goal for a huge class of structures within Conjecture 1 . {theorem} [] (Main theorem) Let \mathbb{A} be a finite-signature first-order expansion of a finitely bounded homogeneous model-complete core \mathbb{B} . Then one of the following holds. • \csp(\mathbb{A}) is L-hard (under first-order reduction). • \csp(\mathbb{A}) is first-order definable, and is in non-uniform \text{AC}^{0} . The difference in the formulation of the above theorem and Conjecture 1 is that in the former case we start with a finitely bounded homogeneous structure \mathbb{B} which is already a model-complete

Read the complete text