Janus-faces of Temporal Constraint Languages: A dichotomy of expressivity
2025
Read Janus-faces of Temporal Constraint Languages: A dichotomy of expressivity (2025) 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-2509-04347.txt.
Introduction
Johanna Brunar and two co-authors prove that certain puzzle-like languages are far less expressive than they appear in a 2025 mathematics paper. The setting is constraint satisfaction, where values must honor a set of rules, extended here to infinite domains. Temporal and phylogeny systems, tied to family trees of species, carry famous complexity classes. Systems failing to build everything turn out to be solvable quickly, a known result the authors deepen.
Such systems can only interpret very limited graphs and hypergraphs through a standard building method. Many algebraic results follow, including special four-ary polymorphisms, symmetry operations that keep solutions valid. Two unlike families share a common proof core. The work supports a major open conjecture in the field.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-04347
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Janus-faces of Temporal Constraint Languages: A dichotomy of expressivity Abstract . The Bodirsky-Kára classification of temporal constraint languages stands as one of the earliest and most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (CSPs), yet it remains one of the most mysterious in terms of algorithms and algebraic invariants for the tractable cases. We show that those temporal languages which do not pp-construct EVERYTHING (and thus by the classification are solvable in polynomial time) have, in fact, very limited expressive power as measured by the graphs and hypergraphs they can pp-interpret. This limitation yields many previously unknown algebraic consequences, while also providing new, uniform proofs for known invariance properties. In particular, we show that such temporal constraint languages admit 4 4 -ary pseudo-Siggers polymorphisms – a result that sustains the possibility that the existence of such polymorphisms extends to the much broader context of the Bodirsky-Pinsker conjecture. When Ianus can’t express it all He tries in vain, he hits a wall When for 𝕂 3 \mathbb{K}_{3} no way he knows His face of pseudo-loops he shows † † footnotetext: The Roman god Janus (Latin: Ianus ), traditionally depicted with two faces looking in opposite directions, embodies the duality of temporal perspective. Funded by the European Union (ERC, POCOCOP, 101071674). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This research was funded in whole or in part by the Austrian Science Fund (FWF) [I5948]. For the purpose of Open Access, the authors have applied a CC BY public copyright licence to any Author Accepted Manuscript (AAM) version arising from this submission. The first author is a recipient of a DOC Fellowship of the Austrian Academy of Sciences at the Technische Universität Wien. Johanna Brunar , Michael Pinsker , and Moritz Schöbi 1. Introduction 1.1. Constraint Satisfaction Problems The Constraint Satisfaction Problem induced by a relational structure \mathbb{A} , denoted by \CSP(\mathbb{A}) , is the computational problem of deciding, given a finite input structure \mathbb{B} of the same signature as \mathbb{A} , whether there exists a homomorphism from \mathbb{B} to \mathbb{A} , i.e. a map preserving all relations. The underlying structure \mathbb{A} will often be referred to as template structure. This notion of fixed-template CSPs provides a uniform framework for modelling many classical computational problems such as graph-colouring problems, 3 -SAT, or solving equations. In 2017, two independent confirmations of a complexity dichotomy for CSPs induced by arbitrary finite structures – conjectured already in [ FV93 , FV98 ] – marked a breakthrough in the research programme on the complexity of finite-domain CSPs: for every finite structure \mathbb{A} , either \CSP(\mathbb{A}) is solvable in polynomial time, or it is NP-complete [ Bul17 , Zhu17 , Zhu20a ] , contrasting Ladner’s theorem [ Lad75 ] . Yet, prominent computational problems that can be phrased as the CSPs of a fixed template \mathbb{A} require the domain of \mathbb{A} to be of countably infinite size – for example, the problem of deciding whether a given finite digraph contains a cycle can be phrased as CSP over (\mathbb{Q};<) , but cannot be modelled in this way by any finite template. There provably does not exist a complexity dichotomy for CSPs with infinite templates, not even if the template is ‘close to finite’ in the sense of \omega -categoricity [ BG08 , GJK+20 ] . For certain countably infinite \omega -categorical structures, namely first-order reducts of finitely bounded homogeneous structures, though, a P/NP-complete complexity dichotomy has been conjectured by Bodirsky and Pinsker more than a decade ago (see [ BPP21 , BP16 , BKO+17 , BKO+19 ] for various formulations of the conjecture). The conjecture remains wide open in its generality, but has been verified for several classes of structures fitting into the conjectured framework, including temporal constraint languages [ BK08b , BK10 ] , equality constraint languages [ BK08a ] , phylogeny CSPs [ BJP16 , BJP17 ] , the universal homogeneous poset [ KP17 , KP18 ] , MMSNP [ BMM18 , BMM21 ] , first-order reducts of any homogeneous undirected graph [ BMPP19 ] including the random graph [ BP15a ] , the universal homogeneous tournament [ MP22 , MP24 ] , and graph orientation problems with forbidden tournaments [ BGP25 , BM24 , FP25 ] . One of the earliest complexity classifications within the scope of the Bodirsky-Pinsker conjecture (which predates the conjecture and most likely inspired it) was obtained for the class of CSPs induced by temporal constraint languages , i.e. structures of the form (\mathbb{Q};R_{1},R_{2},\dots) where each R_{i} has a first-order definition in (\mathbb{Q};<) – the rational numbers with the dense linear order [ BK08b , BK10 ] . To this day, temporal constraint languages remain an active subject of study. They give rise to a natural and important class of CSPs, appearing in prominent problems from artificial intelligence such as temporal and spatial reasoning, see e.g. [ JD97 , BJ03 , KJJ03 , DJ05 , BJM+24 ] . Yet despite their practical importance, temporal CSPs remain among the most challenging and least understood templates within the scope of the Bodirsky–Pinsker conjecture. From an algorithmic perspective, they appear fundamentally different from most other classes for which the Bodirsky-Pinsker conjecture has been verified: the general procedure from [ BM16 ] , which relies on canonical polymorphisms [ BPT13 ] to show polynomial-time solvability of an infinite-domain CSP by reducing the problem to the CSP of a finite template, is not applicable in the temporal case. Moreover, the descriptive complexity of temporal CSPs is known to differ vastly from the finite [ BR22 ] , and their algebraic properties – crucial to the success of the so-called algebraic approach to CSPs – are still largely unknown. While ongoing research aims to gain deeper insight into the cases that are solvable in polynomial time through new algorithmic approaches [ Mot25 ] , our contribution is to shed light on the algebraic aspects. 1.2. The algebraic approach The complexity of finite-domain CSPs is determined by the ‘expressive power’ of the underlying structure \mathbb{A} , which is encoded in the set \Pol(\mathbb{A}) of all compatible finitary operations – the polymorphism clone of \mathbb{A} . The study of the computational complexity of CSPs via the polymorphisms they have is what is now understood as the algebraic approach to CSPs, first developed in [ Jea98 , BJK05 ] and unified by [ BOP18 ] . The finite-domain CSP dichotomy now takes the following form: as the only source of NP-completeness for \CSP(\mathbb{A}) stands the ability of \mathbb{A} to pp-construct EVERYTHING, i.e. every finite structure (see Section 2.1 for the definition of a pp-construction). For the purpose of this paper, we call a structure that pp-constructs EVERYTHING omni-expressive . Every finite structure that lacks this property gives rise to a CSP solvable in polynomial time, and its polymorphism clone satisfies certain symmetries. Here, we say that the polymorphism clone \Pol(\mathbb{A}) of a structure \mathbb{A} satisfies an identity, if the identity is witnessed by operations contained in \Pol(\mathbb{A}) for all evaluations of their arguments. For