Metraipolis › archive › dc_e87e354519cb
Discrete Temporal CSPs et al — arXiv:2610.21967
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.21967
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T10:34:58.195Z
- SHA-256 of the archived text
d0182d6e654c721997319d184125339313cdea2962e8e5a47c6f3831e5d06d07- Stable URL of this page
https://metraipolis.com/documento/dc_e87e354519cb
How to cite
Discrete Temporal CSPs et al — arXiv:2610.21967 — arXiv (en), https://arxiv.org/abs/2610.21967 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e87e354519cb (Metraipolis archive dc_e87e354519cb, sha256 d0182d6e654c721997319d184125339313cdea2962e8e5a47c6f3831e5d06d07)
BibTeX
@misc{dce87e354519cb,
title = {Discrete Temporal CSPs et al — arXiv:2610.21967},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.21967},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e87e354519cb; sha256 d0182d6e654c721997319d184125339313cdea2962e8e5a47c6f3831e5d06d07},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.21967. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We revisit the complexity classification of constraint satisfaction problems (CSPs) for first-order reducts of $(\mathbb{Z},<)$, established by Bodirsky, Martin, and Mottet in 2018. Following their approach, we give a self-contained proof of this classification, correcting several errors in the argument. We further show that, with the exception of cases arising from finite-domain CSPs, all tractable cases are solved by a well-known uniform algorithm, eliminating the need for the collection of ad-hoc algorithms used in the original paper. A central component of the proof allows the analysis to be restricted to first-order reducts of $(\mathbb{Z},<)$ that contain the successor relation. We substantially simplify this reduction and generalize the underlying construction. This generalization allows us to apply the same technique to first-order reducts of the triangular lattice graph and of infinite regular trees, yielding a complete complexity classification for these classes of structures, in particular a $\mathsf{P}$ versus $\mathsf{NP}$-complete dichotomy.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.LO, nuovi lavori del giorno).
Categorie arXiv: Logic (math.LO) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.21967 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T08:51:17.643Z dalla pagina https://arxiv.org/list/math.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).