Source-linked AI summary
A Non-Dichotomy for CSPs of Stable $\omega$-Categorical Structures
Manuel Bodirsky, David Bradley-Williams, Ehud Hrushovski, Christoph Spiess
TL;DR
The paper asks whether stability and ω-categoricity constrain infinite-domain CSP complexity. It constructs and separates stable graph templates and their non-edge expansions, obtaining CSPs across three complexity regimes, including continuum many distinct cases, almost all undecidable.
Problem
The paper asks whether an ω-categorical stable template must have a decidable CSP, and whether such structures can have NP-intermediate CSPs.
Source: §1 · p. 3Method
It uses controlled Hrushovski constructions to build stable, ω-categorical graphs, separates their ages, and expands them by a definable non-edge relation.
Source: §4.2 · p. 10, §7 · p. 17Results
Stable, ω-categorical templates with at most two binary relations have NP-complete, decidable but not in NP, and undecidable CSPs; 2^ℵ0 distinct expansion CSPs are obtained, all but countably many undecidable.
Source: §1 · pp. 3–4, §7 · p. 17Takeaways & Limitations
Stability and ω-categoricity alone impose no uniform bound on CSP complexity.
Source: §1 · p. 3, §7 · p. 17Whether stable ω-categorical templates can have NP-intermediate CSPs remains open.
Source: §7 · p. 17
Abstract
from arXiv · showhide
We construct countable, stable, $\omega$-categorical structures with at most two binary relations whose CSPs exhibit three complexity regimes: NP-complete, decidable but not in NP, and undecidable. The templates arise from a controlled Hrushovski construction of stable $\omega$-categorical graphs $M_\alpha$ for suitable irrational parameters $\alpha>1$. Some of these graphs have NP-complete CSPs. Expanding the graphs $M_\alpha$ by the non-edge relation turns age membership into a restriction of the CSP. For every time-constructible bound $t$, there is such an expansion whose CSP is decidable but not in DTIME$(t)$. For an explicit parameter $\alpha$, the restriction to complete instances belongs to $\mathrm{coNP}$ and the full CSP belongs to $\Sigma_2^{\mathrm P}$. Separating the ages of the $M_\alpha$ using graphs with large girth and prescribed density yields $2^{\aleph_0}$ distinct CSPs of these expansions, all but countably many of which are undecidable.
1 Introduction
The introduction asks whether stability or related model-theoretic tameness can regularize infinite-domain CSPs, and answers negatively with stable, ω-categorical binary templates. A controlled Hrushovski construction and age separation yield distinct CSPs spanning NP-complete, decidable but not in NP, and undecidable cases.
1 Introduction
- Finite-template CSPs obey a P-versus-NP-complete dichotomy [33], [7], [32], whereas unrestricted infinite templates can realize arbitrary computational behavior [3, Theorem 1].The paper asks what structural restrictions can retain classification while allowing genuinely infinite domains.Source: §1 · p. 2
- Stability and therefore NIP do not ensure decidability: the paper constructs stable, ω-categorical templates in a finite binary signature with undecidable CSPs.The examples retain finite orbit structure at every arity and exclude definable order.Source: §1 · p. 3
- Theorem 2 establishes 2^ℵ0 countable stable ω-categorical graphs with pairwise distinct ages; separating graphs use Erdős’s theorem that girth and chromatic number can simultaneously be arbitrarily large [12].Pairwise age separation is stronger than pairwise non-isomorphism and is crucial to the CSP consequences because complete instances encode age membership.Source: §1 · pp. 3–4
- A controlled Hrushovski construction uses irrational parameters α > 1 and a slowly growing control function to produce graphs Mα with specified finite-graph ages.The construction is designed so the control function tends to infinity, yielding bounded closures in terms of finite-set size and supporting ω-categoricity.Source: §1 · pp. 3–4
- Expanding Mα by the non-edge relation makes complete CSP instances test age membership, yielding 2^ℵ0 distinct CSPs, all but countably many undecidable.A complete instance assigns exactly one of edge or non-edge to every distinct vertex pair, forcing homomorphisms to be injective and preserve both relations.Source: §1 · p. 4
- Computable parameters yield decidable CSPs of arbitrarily high deterministic time complexity, with the lower bound already holding on complete instances.The introduction measures input size by the number of variables and describes the parameters as obtained by an effective refinement.Source: §1 · p. 4
- Stable, ω-categorical templates with at most two binary relations exhibit NP-complete, decidable-but-not-in-NP, and undecidable CSPs; the graph reducts are NP-complete on stated parameter ranges.For a suitable computable α, Mα and its non-edge expansion give the first and middle cases; the time lower bound is measured by variables.Source: §1 · pp. 4–5
Outline
The paper moves from constructing stable, ω-categorical graphs to separating their ages and deriving CSP complexity consequences.
Outline
- The background and Sections 2–3 develop the framework and controlled Hrushovski constructions for stable, ω-categorical graphs.Construction details are deferred to appendices A–C.Source: Outline · p. 5
- Section 4 separates ages uniformly on parameter intervals using graphs of high girth and prescribed density.Source: Outline · p. 5
- Section 5 links complete instances of non-edge expansions to age membership and constructs decidable CSPs beyond prescribed time bounds; Section 6 derives graph-reduct complexity results.The Section 6 results use promise-CSP hardness and homomorphic equivalence to finite cliques.Source: Outline · p. 5
2 Preliminaries
The preliminaries fix the structural and logical notions used in the paper, then state the strong-embedding amalgamation framework for constructing countable structures.
2 Preliminaries
- For graphs, substructures are induced, while a subgraph may also delete edges; density is the edge count divided by vertex count.Source: §2 · pp. 5–6
- A CSP fixes a template and asks whether a finite input structure admits a homomorphism to it; an embedding additionally is injective and reflects relations.An age is the class of finite induced substructures, up to isomorphism.Source: §2 · p. 5
- ω-categoricity is equivalent to finitely many automorphism orbits on tuples of each fixed length, and stability excludes the order property; stability implies NIP.Source: §2 · p. 6
- A parameter-free definable expansion preserves ω-categoricity and stability because it retains the automorphism group and cannot introduce the order property.Source: §2 · p. 6
2.1 Constructing countable structures
- An amalgamation class with arbitrarily large members and the stated strong-embedding conditions has a unique countable amalgamation limit with that age and an extension property.Every finite subset lies in a finite strong substructure, and isomorphisms between finite strong substructures extend to automorphisms.Source: §2.1 · p. 7
- A size bound placing every finite subset inside a bounded-size strong substructure supplies the criterion used to obtain ω-categoricity.The bound depends on the size of the subset.Source: §2.1 · p. 7
3 Controlled predimension classes
The construction uses a parameter-dependent control function to define finite graph classes with free amalgamation. When the control function is unbounded, the resulting amalgamation limit is stable and ω-categorical.
3 Controlled predimension classes
- Fα is a strictly increasing, concave control function with Fα(N)/N → 0, used to define the graph predimension.It is formed from rational approximations to α from below and extended linearly between integers.Source: §3 · pp. 7–8
- Cα consists of finite graphs whose nonempty induced subgraphs satisfy the control inequality for their predimension.Deleting edges preserves membership, so the inequality also holds for subgraphs that are not induced.Source: §3 · p. 8
3.1 Free amalgamation
- For irrational α > 1, (Cα, ≤α) is a free-amalgamation class, and Mα is its amalgamation limit.The free amalgam adds no edges between the two parts outside their common induced subgraph.Source: §3.1 · pp. 8–9
3.2 Bounded closures and stability
- Closures have a uniform size bound depending only on the size of the initial set, yielding ω-categoricity of Mα.The closure predimension is no greater than that of the original finite set.Source: §3.2 · p. 9
- For irrational α > 1 with Fα(N) → ∞, the amalgamation limit Mα is stable and ω-categorical.The closure argument gives ω-categoricity; stability is established under the unboundedness condition.Source: §3.2 · p. 9
4 A continuum of distinct ages
There are continuum many admissible parameters for which the control functions are unbounded. High-girth, high-density switch graphs separate the corresponding ages, making the ages pairwise distinct.
4.1 Many admissible parameters
- The admissible parameter set has cardinality 2^ℵ0, and each such parameter has Fα(N) → ∞.The dense-open-set argument yields parameters to which the earlier structural results apply.Source: §4.1 · p. 10
4.2 The switch lemma
- For any g ≥ 3, q > 1, and L, there is a finite graph with at least L vertices, girth greater than g, and more than q times as many edges as vertices.This density consequence supplies graphs used in the separation argument.Source: §4.2 · p. 10
- A switch graph is outside Cα on one parameter interval and inside Cα on another, and can have arbitrarily large girth and size.It can also be chosen with e(G) > u1|G|.Source: §4.2 · p. 10
- The age of Mα determines α through the supremum of e(G)/|G| over graphs G in Cα.Switch graphs establish the reverse bound by providing members of Cα with density exceeding each rational q < α.Source: §4.2 · p. 11
- The resulting stable, ω-categorical graphs have pairwise distinct ages, giving 2^ℵ0 distinct ages.The switch construction distinguishes Cα from Cβ whenever α and β differ.Source: §4.2 · pp. 10–11
5 Constraint satisfaction consequences
Expanding Mα by the definable non-edge relation makes complete CSP instances test age membership, while arbitrary instances can be handled through consistent quotients. These CSPs include decidable problems beyond every time-constructible bound, as well as a continuum-sized family in which all but countably many are undecidable.
5 Constraint satisfaction consequences
- The expansion Bα=(Mα,N) is stable and ω-categorical, and complete instances of its CSP test membership in Age(Mα).On complete inputs, preserving both relations forces an induced embedding; distinct ages therefore give distinct CSP languages.Source: §5 · pp. 11–12
- The expansions yield 2^ℵ0 distinct CSP languages, all but countably many undecidable.There are only countably many languages decidable by Turing machines.Source: §5 · p. 12
- For computable α, exact rational tests decide age membership, and enumerating consistent quotients then decides CSP(Bα).A quotient must satisfy the stated consistency conditions, and its graph must belong to Cα.Source: §5 · pp. 12–13
- For an explicit α between 9 and 10, complete instances are in coNP and the full CSP is in Σ2^P.These upper bounds require polynomial-time comparison of α with rationals of bounded numerator and denominator.Source: §5 · p. 13
5.1 Effective parameters and a time hierarchy
- For every time-constructible t, a computable parameter yields a decidable CSP outside DTIME(t), with the lower bound already holding on complete instances.The construction diagonalizes against clocked machines while keeping the parameter computable and the CSP decidable.Source: §5.1 · p. 15
6 CSP complexity of the graph reducts
The graph reducts are NP-hard for every admissible irrational parameter, and are NP-complete on specified parameter ranges. Adding the non-edge relation can produce CSPs that are undecidable or decidable but outside NP.
6 CSP complexity of the graph reducts
- For α in (1, 5/3) ∪ (2, ∞), CSP(Mα) is equivalent to k-colouring for some k ≥ 3 and is NP-complete.The continuum many templates in these ranges yield exactly countably many distinct CSP languages, all NP-complete.Source: §6 · p. 15
- For every admissible irrational α > 1, CSP(Mα) is NP-hard; for α in (5/3, 2), membership in NP remains unestablished.Theorem 28 bounds Mα between complete graphs, while promise graph-colouring hardness supplies the reduction.Source: §6 · pp. 15–16
- For all but countably many α in A0, adding the non-edge relation changes an NP-complete graph CSP into an undecidable CSP while preserving stability and ω-categoricity.The expansions Bα have pairwise distinct CSPs, all but countably many undecidable.Source: §6 · pp. 16–17
- For suitable computable α, CSP(Bα) is decidable but not in NP, with deterministic running time exceeding a prescribed time-constructible bound.The construction diagonalizes against the bound; an NP algorithm would imply a deterministic algorithm within it.Source: §6 · pp. 16–17
7 Conclusion
The paper constructs stable, ω-categorical graphs with pairwise distinct ages and uses their non-edge expansions to obtain a range of CSP complexities. The results include continuum many distinct CSPs, almost all undecidable, alongside decidable examples outside NP.
7 Conclusion
- The construction gives 2^ℵ0 countable stable ω-categorical graphs with pairwise distinct ages.Their non-edge expansions have pairwise distinct CSPs, all but countably many undecidable.Source: §7 · p. 17
- For suitable computable parameters, the expansion has a decidable CSP outside NP; for all but countably many parameters in the stated range, adding non-edges yields undecidability.Graph reducts are NP-complete on the range (1, 5/3) ∪ (2, ∞).Source: §7 · p. 17
- The cardinality argument does not identify an explicit α with undecidable CSP(Bα), and the computable time-lower-bound parameters come from diagonalisation.For Pantano’s explicit parameter, complete instances belong to coNP and the full CSP belongs to Σ2^P; exact complexity remains unresolved.Source: §7 · p. 17
- Whether stable ω-categorical templates can have NP-intermediate CSPs remains open, including among first-order reducts of Mα.The established non-dichotomy relies on CSPs outside NP.Source: §7 · p. 17
A Construction of the amalgamation limit
The construction builds a countable limit by successively embedding finite members of the class and amalgamating extensions over strong substructures. Controlled predimension calculations support the strong-amalgamation framework used in that construction.
A Construction of the amalgamation limit
- At each stage, the construction embeds the next representative and processes all strong embeddings from earlier stages by successive amalgamations.Finiteness of the structures ensures there are only finitely many embeddings to process at a stage.Source: A Construction of the amalgamation limit · p. 20
- Every class member strongly embeds into the limit, and the limit is countably infinite because the class has arbitrarily large finite structures.The construction also yields uniqueness up to isomorphism and homogeneity restricted to strong substructures.Source: A Construction of the amalgamation limit · p. 20
B Controlled predimension calculations
- The controlled predimension estimates establish that the free amalgam of strong extensions remains an amalgam by strong embeddings.Concavity of the control function supplies an inequality used to combine the bounds in the free amalgam.Source: B Controlled predimension calculations · pp. 21–22
- Repeatedly extending a finite set without increasing predimension terminates in a strong substructure containing it.The smallest strong closure lies inside the resulting extension.Source: B Controlled predimension calculations · p. 22
C Stability of the controlled amalgamation limit
The stability proof uses closure and dimension properties to obtain closed free amalgams, then counts types from countable closed extensions. This establishes stability of the controlled amalgamation limit.
C Stability of the controlled amalgamation limit
- The stability argument counts types over closed parameter sets by representing them through countable closed extensions and dimension independence.The proof establishes stability by showing types are determined by such extensions, whose isomorphism types determine complete types.Source: C Stability of the controlled… · pp. 22–23
- Finite closure is obtained from predimension-minimising extensions, and irrational α ensures a finite set is closed exactly when its dimension equals its predimension.The closure is finite and monotone, with finite character.Source: C Stability of the controlled… · pp. 23–24
- Isomorphisms between closed subgraphs are elementary, and dimension independence yields closed free amalgams.For finite closed sets, any cross-edge would contradict the dimension equality; the argument extends to arbitrary closed sets.Source: C Stability of the controlled… · pp. 26–27
- The proof counts at most 2^ℵ0 finite types over a parameter set of size 2^ℵ0, establishing stability.Countable diagrams together with the identified intersection determine the complete type through closed free amalgamation.Source: C Stability of the controlled… · p. 28
D The open-dense parameter argument
The parameter argument establishes open dense intervals with controlled approximation behavior, alongside constructions that separate graph ages and connect CSP instances to age membership. It also gives effective procedures for the parameter calculations.
D The open-dense parameter argument
- The denominator bound ensures every rational strictly between the specified approximants has denominator at least b + d.The interval construction also avoids admissible rational approximations within the relevant denominator bound, so the strict convention causes no change there.Source: D The open-dense parameter argument · p. 29
- For every nonempty open interval I and m, a rational open subinterval J and K can be chosen so the specified bound holds; the union of such J is open and dense in (1, ∞).Nested disjoint intervals also give a continuous injection of 2^ω into the intersection of the open-dense sets, hence continuum many points there.Source: D The open-dense parameter argument · p. 29
E High girth and density
- For any requested girth and density thresholds, a finite graph can be constructed with at least L vertices, girth greater than g, and more than q|H| edges.The construction starts from a graph of high chromatic number and takes a vertex-minimal subgraph retaining that chromatic number.Source: E High girth and density · p. 30
F CSP and effective parameter calculations
- Complete E- and N-constraint instances map to Bα exactly when their graphs embed inducedly into Mα, so this restriction characterizes Age(Mα).For general instances, a homomorphism is characterized by a consistent kernel quotient whose graph belongs to Cα.Source: F CSP and effective parameter… · p. 31
- For bounded approximation denominators, only finitely many relevant rationals need be considered, yielding an effective decomposition into intervals on which the best lower approximations are fixed.The strict convention can affect values at the finite exceptional rational set, but not on the open components used in the interval construction.Source: F CSP and effective parameter… · p. 31
G A parameter for the polynomial-hierarchy bound
The section presents an explicit irrational parameter in the required class and establishes polynomial-time comparison against it. Its construction uses sparse decimal positions to show irrationality and membership in the class.
G A parameter for the polynomial-hierarchy bound
- The explicit parameter α is irrational, belongs to A, satisfies 9 < α < 10, and permits deciding whether a/b < α in time polynomial in N.The comparison applies to integers a, b satisfying the proposition's stated input bound.Source: G A parameter for the… · pp. 31–32
- The parameter's decimal expansion has increasingly large gaps between nonzero digits, making it irrational; the approximation argument places it in A.For each r, a finite approximation bound persists on a rational open interval around α.Source: G A parameter for the… · p. 32
- The comparison reduces a/b < α to the integer comparison aS < bQ, with the truncation and final comparison computable in polynomial time.The proof bounds the truncation length and the intermediate integers' bit sizes polynomially in N.Source: G A parameter for the… · p. 33
H Finite equivalents for irrational coefficients
The section gives criteria for when Mα is homomorphically equivalent to a finite clique. In the stated parameter ranges, these equivalences identify the CSPs with graph-colouring problems and yield NP-completeness.
H Finite equivalents for irrational coefficients
- If Sα(n) < Dℓ(n) for every n ≥ ℓ, then every finite subgraph is (ℓ−1)-colourable and compactness gives Mα → Kℓ−1.The criterion rules out finite ℓ-critical subgraphs using the edge bound for finite subgraphs of Mα.Source: H Finite equivalents for irrational… · p. 34
- For 1 < α < 5/3, Mα is homomorphically equivalent to K3, so its CSP is graph 3-colouring.The colouring criterion establishes Mα → K3, while Theorem 28 supplies the reverse homomorphism.Source: H Finite equivalents for irrational… · p. 34
- For α > 2, the cases split at βk; in either case Mα is homomorphically equivalent to a finite clique with at least three vertices, making its CSP the corresponding graph-colouring problem and NP-complete.The stated cases give equivalence to Kℓ or Kℓ−1.Source: H Finite equivalents for irrational… · p. 35