When Darwin met Ianus: dichotomies of expressivity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911650819342336 |
|---|---|
| author | Brunar, Johanna Pinsker, Michael Schöbi, Moritz |
| author_facet | Brunar, Johanna Pinsker, Michael Schöbi, Moritz |
| contents | The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (CSPs), yet remain the most mysterious in terms of algorithms and algebraic invariants for the tractable cases. We show that those languages which do not pp-construct EVERYTHING (and thus by the classifications 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 and phylogeny constraint languages admit $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. Although temporal and phylogeny constraint languages appear to follow fundamentally different algorithmic principles, our proofs reveal a common core and proceed along strikingly similar lines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04347 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | When Darwin met Ianus: dichotomies of expressivity Brunar, Johanna Pinsker, Michael Schöbi, Moritz Logic in Computer Science Logic Rings and Algebras The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (CSPs), yet remain the most mysterious in terms of algorithms and algebraic invariants for the tractable cases. We show that those languages which do not pp-construct EVERYTHING (and thus by the classifications 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 and phylogeny constraint languages admit $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. Although temporal and phylogeny constraint languages appear to follow fundamentally different algorithmic principles, our proofs reveal a common core and proceed along strikingly similar lines. |
| title | When Darwin met Ianus: dichotomies of expressivity |
| topic | Logic in Computer Science Logic Rings and Algebras |
| url | https://arxiv.org/abs/2509.04347 |